Articles written in Sadhana
Volume 45 All articles Published: 12 October 2020 Article ID 0255
Branch-and-bound algorithms for scheduling in an m-machine no-wait flowshop
NARAYANAPRASAD MADHUSHINI CHANDRASEKHARAN RAJENDRAN
In this paper, we develop branch-and-bound algorithms for objectives such as sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, for an m-machine no-wait (continuous) flowshop. We believe that there has been no prior work on exact algorithms for this problem setup with a variety of objective functions. For the interest of space, we confine our discussion to a subset of certain combination of these objectives and the extension to other objective combinations is quite straight-forward. We explore the active nodes of a branch-and-bound tree by deriving an assignment-matrix based lower bound, that ensures oneto-one correspondence of a job with its due date and weight. This idea is based on our earlier paper on general m-machine permutation flowshop (Madhushini et al. in J Oper Res Soc 60(7):991–1004, 2009) and here weexploit the intricate features of a no-wait flowshop to develop efficient lower bounds. Finally, we conclude our paper with the numerical evaluation of our branch-and-bound algorithms.
Volume 48, 2023
Continuous Article Publishing mode
Click here for Editorial Note on CAP Mode