Scheduling parallel machines for the customer order problem

Scheduling parallel machines for the customer order problem

0.00 Avg rating0 Votes
Article ID: iaor2008716
Country: United Kingdom
Volume: 8
Issue: 1
Start Page Number: 49
End Page Number: 74
Publication Date: Jan 2005
Journal: Journal of Scheduling
Authors: ,
Keywords: heuristics
Abstract:

This paper considers scheduling problems where jobs are dispatched in batches. The objective is to minimize the sum of the completion times of the batches. While a machine can process only one job at a time, multiple machines can simultaneously process jobs in a batch. This simple environment has a variety of real world applications such as part kitting and customer order scheduling. A heuristic is presented for the parallel machine version of the problem. Also, a tight worst case bound on the relative error is found. For the case of two parallel machines, we examine two heuristics, which are based on simple scheduling rules. We find tight worst case bounds of 6/5 and 9/7 on the relative error and show that neither procedure is superior for all instances. Finally, we empirically evaluate these two heuristics. For large problems, the methods find solutions that are close to optimal.

Reviews

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