Time complexity and linear-time approximation of the ancient two-machine flow shop

Time complexity and linear-time approximation of the ancient two-machine flow shop

0.00 Avg rating0 Votes
Article ID: iaor2000828
Country: United Kingdom
Volume: 1
Issue: 3
Start Page Number: 149
End Page Number: 155
Publication Date: Oct 1998
Journal: Journal of Scheduling
Authors: ,
Keywords: flowshop
Abstract:

We consider the scheduling problems F2∥Cmax and F2|no-wait|Cmax, i.e. makespan minimization in a two-machine flow shop, with and without no wait in process. For both problems solution algorithms based on sorting with O(n log n) running time are known, where n denotes the number of jobs. We prove that no asymptotically faster algorithms can solve these problems. This is done by establishing Ω(n log n) lower bounds in the algebraic computation tree model of computation. Moreover, we develop for every ϵ > 0 approximation algorithms with linear running time 0(n log(1/ϵ)) that deliver feasible schedules whose makespan is at most 1 + ϵ times the optimum makespan.

Reviews

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