Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs. Issue 6 (3rd June 2017)

• Record Type: Journal Article
• Authors: Huang, J. D.; Liu, J. J.; Chen, Q. X.; Mao, N.
• Is Part Of: Engineering optimization. Volume 49:Issue 6(2017)
• Page Start: 1010
• Page End: 1023
• Publication Date: 2017-06-03
• Subjects: Batch scheduling -- flow shop -- heuristics -- re-entrant -- heat treatment; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2016.1231307
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.