A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem
In this paper, a two-stage assembly scheduling problem is considered with the objective of minimizing the total weighted flowtime. A lower bounding procedure and a dominance criterion are developed and incorporated into a branch and bound procedure. A heuristic procedure is also used to derive an initial upper bound. Computational results of the algorithm are presented. Scope and purpose statement The two-stage assembly scheduling problem is a generalization of the two-machine flowshop problem, which has received attention in the literature recently. In the first stage, there are m?1 machines assigned to produce m?1 different types of component, which is required for each job. In the second stage, an assembly machine is used to assemble the components. Each machine can process only one job at any time. The objective is to minimize the sum of weighted completion times (total weighted flowtime) of all jobs. We develop a branch and bound algorithm to solve the problem. Lower bounds and a dominance criterion are incorporated in the algorithm to improve its efficiency. We also conduct computational experiments, which show that the algorithm can solve moderate sized problems in reasonable amount of time. The algorithm could be used to provide a benchmark for the evaluation of heuristics for larger sized problems. This problem appears in many real world situations. Examples are plenty in papers published by prominent researchers.
branch and bound algorithm total weighted flowtime scheduling two-stage assembly flowshop