Premium
Single‐machine scheduling to minimize absolute deviation of completion times from a common due date
Author(s) -
Szwarc Wlodzimierz
Publication year - 1989
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(198910)36:5<663::aid-nav3220360510>3.0.co;2-x
Subject(s) - scheduling (production processes) , single machine scheduling , absolute deviation , computer science , mathematical optimization , due date , mathematics , upper and lower bounds , branch and bound , job shop scheduling , statistics , schedule , mathematical analysis , operating system
The article considers a single‐machine n ‐job scheduling problem to minimize the sum of absolute lateness given a common due date. Two models are defined depending on whether the start time t 0 of schedules is arbitrary or fixed. Conditions are provided when those two models coincide. The developed branch‐and‐bound procedure is tested on nine known examples from the literature (6 ⩽ n ⩽ 14) and 90 medium‐size random problems (15 ⩽ n ⩽ 25) with a fixed t 0 .