Continuous slab caster scheduling and interval graphs

Abstract

We define and solve a scheduling problem for operating the continuous steel slab caster which converts molten steel into slabs. The nature of our problem has an interesting connection to a special class of graphs known as interval graphs. We show that our problem can be seen as a variant of the clique partitioning problem defined on interval graphs and develop an optimal algorithm for it.

Keywords:

• Continuous caster
• scheduling
• interval graph
• clique partitioning

Acknowledgments

KANGBOK LEE has earned BS (1998) and MS degrees (2000) in Industrial Engineering and is currently enrolled in the PhD programme at Pohang University of Science and Technology (POSTECH) in Korea. His main research interest is in combinatorial optimization problems in scheduling and graph theory. He is expected to graduate with his PhD degree in the year 2004. He has had a few research papers accepted and under review in several journals, including Computers & Operations Research, Discrete Applied Mathematics and International Journal of Industrial Engineering. He has extensive experience in developing various production scheduling and logistic planning systems for the steel industry in Korea.

SOO Y. CHANG is an Associate Professor in the Department of Industrial Engineering at POSTECH in Korea. He teaches linear programming, discrete optimization, network flows and operations research courses. His research interests include mathematical programming, scheduling and financial engineering. He has published in several journals, including Production Planning & Control, Discrete Applied Mathematics, IIE Transactions and International Journal of Production Research. He is a member of INFORMS, Korean IIE and ORMSS.

YUSHIN HONG is a Professor in the Department of Industrial Engineering at POSTECH in Korea. He teaches production planning and control, dynamic systems, decision analysis and operations research courses. His research interests include production planning, scheduling and control, manufacturing systems analysis and operations research applications. He has published in several journals, including Production Planning & Control, IIE Transactions, International Journal of Production Research, European Journal of Operational Researches and International Journal of Production Economics. He is a member of IIE, INFORMS, APORS, Korean IIE and Korean ORMSS.