Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10348496 | Computers & Operations Research | 2005 | 17 Pages |
Abstract
This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Ching-Fang Liaw, Chun-Yuan Cheng, Mingchih Chen,