A Hungarian penalty-based construction algorithm to minimize makespan and total flow time in no-wait flow shops. (August 2016) - Laha, Dipak; Gupta, Jatinder N.D.
Highlights: We solve the no-wait flowshop problems with makespan and mean flowtime objectives. For the first time, we use the adapted Hungarian Method to find an initial solution. We show that proposed method is superior to state-of-art existing algorithms. We suggest some directions for fruitful future research. Abstract: This paper presents a penalty-based construction algorithm for the no-wait flow shop scheduling problem with the objective of minimizing makespan and total flow time of jobs. The proposed method, derived from Hungarian penalty method originally used for the classic assignment problem is employed to generate an initial schedule of jobs, which is further improved by an insertion technique to obtain an optimal or near-optimal schedule. The results of computational experiments on a large number of test problems show that the proposed method performs significantly better than the state-of-the-art procedures while requiring comparable computational effort.