Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 35, Issue 10, Pages 3276-3283Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2007.02.017
Keywords
scheduling; no-wait; job shop; tabu search; heuristic
Ask authors/readers for more resources
This paper examines the problem of scheduling two-machine no-wait job shops to minimize makespan. The problem is known to be strongly NP-hard. A two-phase heuristic is developed to solve the problem. Phase I of the heuristic transforms the problem into a no-wait flow shop problem and solves it using the well known Gilmore and Gomory algorithm. Phase 2 of the heuristic improves the solution obtained in phase I using a simple tabu search algorithm. Computational results show that the proposed heuristic performs extremely well in terms of both solution quality and computation time. It finds an optimal solution to about 90% of the problem instances and the average deviation from the lower bond for the other problem instances is infinitesimal. (c) 2007 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available