Premium
Optimal timing schedules in earliness‐tardiness single machine sequencing
Author(s) -
Szwarc Wlodzimierz,
Mukhopadhyay Samar K.
Publication year - 1995
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(199510)42:7<1109::aid-nav3220420709>3.0.co;2-5
Subject(s) - tardiness , computer science , due date , schedule , idle , scheduling (production processes) , mathematical optimization , sequence (biology) , job shop scheduling , mathematics , operating system , biology , genetics
The article deals with a single machine earliness‐tardiness scheduling model where idle times are permitted in job processing. Based on a cluster concept we develop properties of the model that lead to a very fast algorithm to find an optimal timing schedule for a given sequence of jobs. The performance of this algorithm is tested on 480 randomly generated problems involving 100, 200, 400 and 500 jobs. It takes less than two seconds to solve a 500 job problem on a PC. © 1995 John Wiley & Sons, Inc.