Journal
ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING
Volume 25, Issue 3, Pages 667-679Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.rcim.2008.05.003
Keywords
Heuristics; Batch-processing machines; Scheduling; Flow shop; Simulated annealing
Ask authors/readers for more resources
This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver. (C) 2008 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