A Hungarian penalty-based construction algorithm to minimize makespan and total flow time in no-wait flow shops. (August 2016)

• Record Type: Journal Article
• Authors: Laha, Dipak; Gupta, Jatinder N.D.
• Is Part Of: Computers & industrial engineering. Volume 98(2016)
• Page Start: 373
• Page End: 383
• Publication Date: 2016-08
• Subjects: Scheduling -- No-wait flow shops -- Makespan -- Total flow time -- Construction algorithm -- Hungarian penalty based heuristic -- Insertion heuristic -- Traveling salesman problem -- Optimization; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2016.06.003
• Languages: English
• ISSNs: 0360-8352

Abstract

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.