Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed

Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed

0.00 Avg rating0 Votes
Article ID: iaor20022266
Country: United Kingdom
Volume: 29
Issue: 3
Start Page Number: 275
End Page Number: 294
Publication Date: Mar 2002
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

This paper considers a scheduling problem for a two-machine flowshop where a discrete processing machine is followed by a batch processing machine and a finite number of jobs arrive dynamically at the first machine. In the flowshop, the discrete processing machine processes one job at a time and the batch processing machine processes a batch of jobs simultaneously. The objective is to find the optimal schedule which minimizes the maximum completion time (makespan) of all jobs. In the situation where preemption is allowed on the discrete processing machine, it is shown that the optimal schedule can be found in polynomial time. However, in the situation where no preemption is allowed on the discrete processing machine, it is shown that the problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its tight worst-case error bound is derived. Numerical experiments show that the heuristic algorithm consistently generates good schedules.

Reviews

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