Novel properties along with solution methods for permutation flowshop scheduling


1 Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran


This paper deals with permutation flowshop scheduling to minimize makespan. Some novel useful definitions and properties are established. Then, the paper proposes novel solution methods. Particular attention is paid to algorithms based on the orderings of pairs of jobs. The first algorithm is for three-machine problems and gives optimal solution in a certain strict sense in the case of the ordering of two jobs. Moreover, the paper extends the three-machine Johnson’s rule to the general case of m-machine problems.