AN APPROXIMATION ALGORITHM FOR THE M-MACHINE PERMUTATION FLOW-SHOP SCHEDULING PROBLEM WITH CONTROLLABLE PROCESSING TIMES

The paper deals with the m-machine permutation flow shop scheduling problem in which job processing times, along with a processing order, are decision variables. It is assumed that the cost of processing a job on each machine is a linear function of its processing time and the overall schedule cost to be minimized is the total processing cost plus maximum completion time cost. A 4/3=approximation algorithm for the problem with m = 2 is provided; the best approximation algorithm until now has a worst-case performance ratio equal to 3/2. An extension to the m-machine (m greater-than-or-equal-to 2) permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to 1/2(rho + square-root rho(m - 1)) + 1/4 + O(1/square-root rhom), where rho is the worst-case performance ratio of a procedure used, in the proposed algorithm, for solving the (pure) sequencing problem. Moreover, examples which achieve this bound for rho = 1 are also presented.