Batching and scheduling in a continuous-discrete hybrid flowshop: Lagrangian relaxation-based heuristic algorithms

ABSTRACT

We study a two-stage hybrid flow shop problem arising from a fine chemicals production facility, where the first stage is a continuous chemical reaction process and the second stage is a discrete filling-packaging process. The objective is to minimise the total weighted completion time through batching of the jobs and scheduling of the batches at first stage and scheduling of the jobs at second stage. We formulate the problem as a mixed integer programming model and develop a Lagrangian relaxation-based framework for solving it, where the original problem is decomposed into family-level subproblems, and each subproblem is transformed into a set-partitioning problem. The subproblems are solved to optimality via branch and price algorithm. We also propose two heuristic algorithms for reducing computational efforts without much loss of solution quality. Finally, we conduct computational experiments with both randomly generated and real data sets to test the performance of the three proposed algorithms and demonstrate that the algorithms perform efficiently.

KEYWORDS:

• Hybrid flow shop
• batching and scheduling
• lagrangian relaxation
• branch and price
• heuristic algorithm
• mixed integer program

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that support the findings of this study are available from the corresponding author, upon reasonable request.

Additional information

Funding

This work was supported by Program of Shanghai Subject Chief Scientist, Grant/ Award Number: 16XD1401700.

Notes on contributors

Zhaohui Li

Zhaohui Li is a PhD candidate in Antai College of Economics and Management, Shanghai Jiao Tong University. Her research interests are operations and supply chain management, and business analytics.

Guohua Wan

Guohua Wan is a distinguished professor at Antai College of Economics and Management, Shanghai Jiao Tong University. His research interests are operations and supply chain management, healthcare management, and business analytics. He has published extensively on these topics in journals such as Management Science, Operations Research, Mathematics of Operations Research, Production and Operations Management, INFORMS Journal on Computing, Naval Research Logistics, IISE Transactions, European Journal of Operational Research, and International Journal of Production Research. He currently serves as a Senior Editor of Production and Operations Management.