5/3-approximation algorithm for scheduling three-crane integrated scheduling problem

2018 3rd International Conference on Insulating Materials, Material Application and Electrical Engineering

材料科学;无线电电子学;电工学

Xie, Xie^1 ; Zhou, Li^2 ; Zheng, Yongyue^3

Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang 3, China^1

China National Institute of Standardization, Beijing

100191, China^2

Liaoning Institute of Standardization, Shenyang

110004, China^3

关键词: Completion time;    Integrated scheduling;    Iron and steel companies;    Iron-and-steel making;    Loading operations;    Makespan;    Problem structure;    Worst-case performance;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/452/4/042106/pdf
DOI  :  10.1088/1757-899X/452/4/042106

学科分类：材料科学（综合）

来源: IOP

【 摘 要 】

In this paper, we deal with a three-crane integrated scheduling problem arising in a finery shop of an iron and steel making enterprise. It is commonly occurred in every large iron and steel company. The main objective of this process is to determine the sequence of loading operations so that the makespan of all required refined melted steel in ladles, that is, the latest finery completion time among all ladles of the melted steel, is minimized. By exploring the problem structure, an effective heuristic algorithm is designed to solve the problem. We prove that the worst case performance of the heuristic algorithm is 5/3. The results show that the proposed heuristic algorithm is capable of generating good quality solutions.