Scheduling job families about an unrestricted common due date on a single machine

Date

1997-01-01

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

193
views

0
downloads

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 due date. In this paper, we generalize properties from the literature that characterize the structure of an optimal schedule, present a lower bound, propose a branch and bound algorithm and a beam search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for smaller problem instances. For large problems, we find high quality solutions within a few minutes of CPU time.

Subject Keywords

Complexity, Earliness, Setup times, Tardiness penalties

URI

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

Journal

International Journal of Production Research

DOI

https://doi.org/10.1080/002075497195344

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates Azizoğlu, Meral (Informa UK Limited, 1997-11-01) We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an op...
Scheduling jobs on unrelated parallel machines to minimize regular total cost functions Azizoğlu, Meral; Kirca, O (1999-02-01) In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived sp...
Dynamic programming algorithms for scheduling parallel machines with family setup times Webster, Scott; Azizoğlu, Meral (Elsevier BV, 2001-2) 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...
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

M. Azizoğlu, “Scheduling job families about an unrestricted common due date on a single machine,” International Journal of Production Research, pp. 1321–1330, 1997, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47275.