Tight bounds for permutation flow shop scheduling

Tight bounds for permutation flow shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor200968822
Country: United States
Volume: 34
Issue: 2
Start Page Number: 417
End Page Number: 427
Publication Date: May 2009
Journal: Mathematics of Operations Research
Authors: ,
Keywords: flowshop
Abstract:

In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,…,m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs σ [n] maps to [n] that minimizes the maximum job completion time (makespan) of the schedule resulting from σ. The previously best known approximation guarantee for this problem was O((m log m)1/2) (2004). In this paper, we obtain an improved O(min{m1/2,n1/2}) approximation algorithm for the permutation flow shop scheduling problem, by finding a connection between the scheduling problem and the longest increasing subsequence problem. Our approximation ratio is relative to the lower bounds of maximum job length and maximum machine load, and is the best possible such result. This also resolves an open question from Potts et al. (1991), by algorithmically matching the gap between permutation and nonpermutation schedules.

Reviews

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