Heuristic for no-wait flow shops with makespan minimization
Authors:
- 17 March 2008
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 46 (9) , 2519-2530
Abstract
No-wait or constrained flow shops with makespan minimization are considered in this paper. An Objective Increment method is introduced to judge whether or not a new schedule is better than its parent. The judgment is made just by the makespan increment rather than by the traditional method to compute the whole makespan, and the time complexity of a heuristic can be decreased by one order. As a new schedule is usually generated by insertion or pair wise exchanging, objective increments are analysed for the fundamental operations. A composite heuristic is proposed for the problems considered. Experimental results show that the proposed approach outperforms the best existing algorithms with the least CPU time.Keywords
This publication has 14 references indexed in Scilit:
- Inter-agent cooperation and communication for agent-based robust dynamic scheduling in steel productionAdvanced Engineering Informatics, 2004
- An efficient constructive heuristic for flowtime minimisation in permutation flow shopsOmega, 2003
- New heuristics for no-wait flowshops to minimize makespanComputers & Operations Research, 2003
- N∗—an agent-based negotiation algorithm for dynamic scheduling and reschedulingAdvanced Engineering Informatics, 2003
- New heuristics to minimize total completion time in m-machine flowshopsInternational Journal of Production Economics, 2002
- Distributed manufacturing scheduling using intelligent agentsIEEE Intelligent Systems, 2002
- An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobsEuropean Journal of Operational Research, 1997
- A Survey of Machine Scheduling Problems with Blocking and No-Wait in ProcessOperations Research, 1996
- Heuristic algorithms for scheduling in the no-wait flowshopInternational Journal of Production Economics, 1993
- A heuristic algorithm for the m-machine, n-job flow-shop sequencing problemOmega, 1983