Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

Date

2011-01-01

Author

Ozlen, M.
Azizoğlu, Meral

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

213
views

0
downloads

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions. Journal of the Operational Research Society (2011) 62, 152-164. doi:10.1057/jors.2009.157 Published online 3 February 2010

Subject Keywords

Marketing, Management Science and Operations Research, Strategy and Management, Management Information Systems

URI

https://hdl.handle.net/11511/47321

Journal

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

DOI

https://doi.org/10.1057/jors.2009.157

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Generating all efficient solutions of a rescheduling problem on unrelated parallel machines Ozlen, Melih; Azizoğlu, Meral (Informa UK Limited, 2009-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and stability measures. Our efficiency measure is the total flow time and stability measure is the total reassignment cost caused by the differences in the machine allocations in the initial and new schedules. We propose a branch and bound algorithm to generate all efficie...
JOB-SHOP SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (JSTOR, 1994-08-01) In this paper we consider the job shop scheduling problem under a discrete non-renewable resource constraint. We assume that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period. We develop an approximation algorithm for this problem and empirically test its effectiveness in finding the minimum makespan schedules.
Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed Azizoğlu, Meral; Koksalan, SK (Informa UK Limited, 2003-06-01) We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algori...
Spread time considerations in operational fixed job scheduling Eliiyi, D. T.; Azizoğlu, Meral (Informa UK Limited, 2006-10-15) In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance c...
Working time constraints in operational fixed job scheduling Eliiyi, Deniz Tuersel; Azizoğlu, Meral (Informa UK Limited, 2010-01-01) In this study we consider the operational fixed job scheduling problem under working time limitations. The problem has several practical implications in both production and service operations; however the relevant research is scarce. We analyse pre-emptive and non pre-emptive versions of the problem and its special cases. We provide polynomial-time algorithms for some special cases. We show that the non pre-emptive jobs problem is strongly NP-hard, and propose a branch-and-bound algorithm that employs effic...

Citation Formats

M. Ozlen and M. Azizoğlu, “Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 152–164, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47321.