Dynamic programming algorithms for scheduling parallel machines with family setup times

Date

2001-2

Author

Webster, Scott
Azizoğlu, Meral

Metadata

Show full item record

Item Usage Stats

291
views

0
downloads

We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms - a backward algorithm and a forward algorithm - and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms. Scope and purpose While most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models. (C) 2000 Elsevier Science Ltd. All rights reserved. We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms - a backward algorithm and a forward algorithm - and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms.

Subject Keywords

Production scheduling, Dynamic programming, Family setup times

URI

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

Journal

Computers & Operations Research

DOI

https://doi.org/10.1016/s0305-0548(99)00094-5

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

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...
Parallel machine scheduling with family setup times to minimize total flowtime Azizoğlu, Meral; Kondakci, Suna (International Forum of Management Scholars (INFOMS), 2002-12-01) In this study, we consider parallel machine scheduling problem with family setup times. Our criterion is to minimize total flowtime. We develop a branch and bound algorithm using an efficient branching scheme and powerful lower and upper bounds. Our computational experiment has shown that the algorithm finds optimal solutions to moderate-sized problems in reasonable CPU times.
Scheduling job families about an unrestricted common due date on a single machine Azizoğlu, Meral (1997-01-01) We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup; a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its ...
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.
On the minimization of total weighted flow time with identical and uniform parallel machines Azizoğlu, Meral (1999-02-16) 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.

Citation Formats

S. Webster and M. Azizoğlu, “Dynamic programming algorithms for scheduling parallel machines with family setup times,” Computers & Operations Research, pp. 127–137, 2001, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/28263.