This 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 -approximation algorithm for the problem with is provided; the best approximation algorithm until now has a worst-case performance ratio equal to . An extension to the m-machine permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to , where 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 are also presented.
