An empirical analysis of integer programming formulations for the permutation flowshop

An empirical analysis was conducted to assess the relative effectiveness of four integer programming models for the regular permutation flowshop problem. Each of these models was used to solve a set of 60 flowshop problems. Analysis of the resultant computer solution times for each model indicated that the two assignment problem based models solved these problem instances in significantly less computer time than either of the two dichotomous constraints based models. Further, these computer solution time differences increased dramatically with increased numbers of jobs and machines in the flowshop problem. These results contradict Pan's conclusion that a variant of Manne's dichotomous constraints approach was superior to the assignment problem approaches of Wagner and Wilson because the Manne model required less than half of the binary integer variables required by the assignment problem based models.