Generating all efficient solutions of a rescheduling problem on unrelated parallel machines

Download

index.pdf

Date

2009-01-01

Author

Ozlen, Melih
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

263
views

107
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 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 efficient solutions with respect to our efficiency and stability measures. We improve the efficiency of the algorithm by incorporating powerful reduction and bounding mechanisms. Our computational tests on large sized problem instances have revealed the satisfactory behaviour of our algorithm.

Subject Keywords

Management Science and Operations Research, Strategy and Management, Industrial and Manufacturing Engineering

URI

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

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

DOI

https://doi.org/10.1080/00207540802043998

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-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 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 follo...
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...
Scheduling parallel machines to minimize weighted flowtime with family set-up times Azizoğlu, Meral (Informa UK Limited, 2003-01-01) We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time.
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...
Rebalancing the assembly lines with total squared workload and total replacement distance objectives Girit, Utku; Azizoğlu, Meral (Informa UK Limited, 2020-01-01) Assembly line balancing is an important and well recognised operations research problem. The current line balance may not stay optimal, even feasible, due to the disruptions in one or more workstations. In this study, after the disruption, we aim to rebalance the assembly line by considering the trade-off between workload balancing (fairness measure) and total replacement distance for the tasks assigned to the different workstations (stability measure). We try to generate all non-dominated objective functio...

Citation Formats

M. Ozlen and M. Azizoğlu, “Generating all efficient solutions of a rescheduling problem on unrelated parallel machines,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, pp. 5245–5270, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/49240.