A new heuristic for three-machine flow shop scheduling
UNSPECIFIED (1996) A new heuristic for three-machine flow shop scheduling. OPERATIONS RESEARCH, 44 (6). pp. 891-898. ISSN 0030-364XFull text not available from this repository.
This paper considers the problem of sequencing n jobs in a three-machine flow shop with the objective of minimizing the makespan, which is the completion time of the last job. An O(n log n) time heuristic that is based on Johnson's algorithm is presented. It is shown to generate a schedule with length at most 5/3 times that of an optimal schedule, thereby reducing the previous best available worst-case performance ratio of 2. An application to the general flow shop is also discussed.
|Item Type:||Journal Article|
|Subjects:||H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management|
|Journal or Publication Title:||OPERATIONS RESEARCH|
|Publisher:||INST OPERATIONS RESEARCH MANAGEMENT SCIENCES|
|Number of Pages:||8|
|Page Range:||pp. 891-898|
Actions (login required)