On the minimization of total weighted flow time with identical and uniform parallel machines

Date

1999-02-16

Author

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

227
views

0
downloads

We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.

Subject Keywords

Branch and bound, Parallel machines, Scheduling

URI

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/s0377-2217(97)00427-x

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Preemptive scheduling on identical parallel machines subject to deadlines Azizoğlu, Meral (2003-07-01) We consider the problem of scheduling n preemptive jobs with deadlines on in identical parallel machines so as to minimize total completion time. We show that the problem is polynomially solvable when the processing times and deadlines are agreeable.
Tardiness minimization on parallel machines Azizoğlu, Meral (1998-07-01) We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total tardiness. We present properties that characterize the structure of an optimal schedule. We propose a branch and bound algorithm that incorporates the properties along with an efficient lower bounding scheme.We find that optimal solutions can be obtained in reasonable times for problems with up to 15 jobs. In the last part of the study we extend the results to uniform parallel machines.
Uniform Parallel machine scheduling with family set-up times Tamer, Meral; Azizoğlu, Meral; Azizoğlu, Meral; Department of Industrial Engineering (2003) In this study, we address the scheduling problem of uniform parallel machines with family set-up times so as to minimize the total completion time. We develop a branch and jound algorithm that employs an efficient branching scheme. A bounding mechanism is jroposed to increase the efficiency of this algorithm. Our computational experiment shows hat the optimal solution is found in reasonable CPU times up to 15 jobs. Further experiments »re conducted to test the bounding mechanisms and this experiment indicat...
Using genetic algorithms for single-machine bicriteria scheduling problems Köksalan, Mustafa Murat; Keha, AB (2003-03-16) We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second probl...
Rescheduling of identical parallel machines under machine eligibility constraints Alagoz, O; Azizoğlu, Meral (2003-09-16) In this study, we address a rescheduling problem in parallel machine environments under machine eligibility constraints. We consider total flow time as efficiency measure and the number of jobs processed on different machines in the initial and revised schedules as a stability measure. We present an optimizing algorithm for minimizing the stability measure subject to the constraint that the efficiency measure is at its minimum level. We then propose several heuristic procedures to generate a set of approxim...

Citation Formats

M. Azizoğlu, “On the minimization of total weighted flow time with identical and uniform parallel machines,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 91–100, 1999, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41915.