Branch-and-bound algorithms for scheduling in an m -machine no-wait flowshop
- PDF / 503,788 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 32 Downloads / 216 Views
Ó Indian Academy of Sciences Sadhana(0123456789().,-volV)FT3 ](0123456789().,-volV)
Branch-and-bound algorithms for scheduling in an m-machine no-wait flowshop NARAYANAPRASAD MADHUSHINI1 and CHANDRASEKHARAN RAJENDRAN2,* 1
ExxonMobil Research and Engineering, Spring, TX, USA Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, India e-mail: [email protected]; [email protected]
2
MS received 28 November 2019; revised 28 April 2020; accepted 3 June 2020 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 mmachine 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 mmachine 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. Keywords. Manufacturing; no-wait flowshops; weighted flowtime; weighted tardiness; weighted earliness; branch-and-bound algorithm.
1. Introduction A general mmachine permutation flowshop is a manufacturing system that contains njobs to be scheduled among msequential machines. In this system, every machine performs a different operation on a job with an unlimited wait allowed between the operations. This basic assumption of wait between machines render the schedule unrealistic and impractical in certain scenarios, leading to a different class of flowshops known as no-wait flowshops, also known as continuous flowshops. Here, once the processing of a job begins in the first machine, subsequent processing of that job must be carried out without any delay in the passage of jobs between machines. If necessary, the start of a job on the first machine can be delayed to ensure the continuous flow of jobs in the subsequent machines. Applications of such no-wait flowshops can be found in many industries like chemical refineries, steel factories, pharmaceuticals, food processing, semiconductor manufacturing where the process cannot be interrupted in between. There is quite a significant amount of work done in the field of no-wait flowshop with makespan and total flowtime objectives. But we believe that the due-date based objectives are perhaps more important in real life and are gaining importance in no-wait scheduling practices. We *For correspondence
proposed branch-and-bound algorithms for an mmachine permu
Data Loading...
