Scheduling two-machine no-wait open shops to minimize makespan |
| |
Affiliation: | 1. School of Economics and Management, Southeast University, Nanjing 210096, China;2. School of Science, East China Institute of Technology, Fuzhou, Jiangxi 344000, China |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|