Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs

The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. Branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm.