A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size

A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size

0.00 Avg rating0 Votes
Article ID: iaor20001543
Country: United States
Volume: 29
Issue: 9
Start Page Number: 101
End Page Number: 126
Publication Date: May 1999
Journal: Mathematical and Computer Modelling
Authors: , ,
Keywords: markov processes
Abstract:

In this paper, we propose different heuristic algorithms for flow shop scheduling problems, where the jobs are partitioned into groups or families. Jobs of the same group can be processed together in a batch but the maximal number of jobs in a batch is limited. A setup is necessary before starting the processing of a batch, where the setup time depends on the group of the jobs. In this paper, we consider the case when the processing time of a batch is given by the maximum of the processing times of the operations contained in the batch. As objective function we consider the makespan as well as the weighted sum of completion times of the jobs. For these problems, we propose and compare various constructive and iterative algorithms. We derive suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on different types of local search algorithms. Except for standard metaheuristics, we also apply multilevel procedures which use different neighbourhoods within the search. The algorithms developed have been tested in detail on a large collection of problems with up to 120 jobs.

Reviews

Required fields are marked *. Your email address will not be published.