A new formulation and solution of the flowshop scheduling problem with no in-process waiting (Q1090230)

The flowshop problem for M machines and N jobs is discussed. It is supposed that there is no in-process waiting, i.e. if the processing of job i begins at the moment \(t^ o_ i\) and \(t_{ik}\) is the processing time of job i on machine k then for every feasible schedule the processing of job i must be finished at the moment \(t^ o_ i+\sum^{M}_{k=1}t_{ik}\). The authors consider three criteria simultaneously: makespan, mean flowtime and machine idle time. The problem is formulated as a mixed-integer linear goal programming problem. For this purpose the following goal constraints are added to the ordinary linear programming constraints: \(F_ 1(s)+d^-_ 1-d^+_ 1=G_ 1\), \(F_ 2(s)+d^-_ 2-d^+_ 2=G_ 2\), \(F_ 3(s)+d^-_ 3-d^+_ 3=G_ 3\), where \(F_ 1(s)\), \(F_ 2(s)\), \(F_ 3(s)\) are makespan, mean flowtime and machine idle time, respectively, for a schedule s, \(G_ L\) are goal levels of criteria, \(d^-_ L\), \(d^+_ L\) are deviation variables, \(L=1,2,3\). The objective function is \(Z=P_ 1d^+_ 1+P_ 2d^+_ 2+P_ 3d^+_ 3\), where \(P_ L\) are priority levels.