Premium
Adjacent orderings in single‐machine scheduling with earliness and tardiness penalties
Author(s) -
Szwarc Wlodzimierz
Publication year - 1993
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199303)40:2<229::aid-nav3220400207>3.0.co;2-r
Subject(s) - tardiness , upper and lower bounds , mathematical optimization , branch and bound , scheduling (production processes) , scheme (mathematics) , computer science , schedule , due date , branching (polymer chemistry) , retard , single machine scheduling , job shop scheduling , mathematics , algorithm , psychology , mathematical analysis , materials science , psychiatry , composite material , operating system
This article deals with a single‐machine n job earliness‐tardiness model with job‐independent penalties. It demonstrates that the arrangement of adjacent jobs in an optimal schedule depends on a critical value of the start times. Based on these precedence relations, the article develops criteria under which the problem can be decomposed into smaller subproblems. The branching scheme that used the developed results was tested on 70 examples of size n = 10. This scheme should be incorporated in any branch‐and‐bound method once a lower bound is found. The branching scheme can easily handle small problems without a lower bound. © 1993 John Wiley & Sons, Inc.