Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

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.

KEYWORDS:

• Batch scheduling
• flow shop
• heuristics
• re-entrant
• heat treatment

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant numbers 51205068, 71572049, 61573109] and JieYang City Science and Technology Plan Projects [grant number 2015B01026].