Options
Branch-and-bound algorithms for scheduling in an m-machine no-wait flowshop
Date Issued
01-12-2020
Author(s)
Madhushini, Narayanaprasad
Indian Institute of Technology, Madras
Abstract
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 one-to-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 we exploit 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
45