Volume 57, Number 3, May-June 2023
|Page(s)||1267 - 1284|
|Published online||14 June 2023|
Approximation algorithms for scheduling single batch machine with incompatible deteriorating jobs
School of Management, Hefei University of Technology, Hefei 230009, P.R. China
2 Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, P.R. China
3 School of Electrical Engineering and Automation, Hefei University of Technology, Hefei 230009, P.R. China
* Corresponding author: firstname.lastname@example.org
Accepted: 30 March 2023
Motivated by the soaking process under separate heating mode in iron and steel enterprises, we study the parallel batch machine scheduling problem with incompatible deteriorating jobs. The objective is to minimize makespan. A soaking furnace can be seen as a parallel batch processing machine. In order to avoid the thermal stress caused by excessive temperature difference, initial temperature is needed for the ingot before processing. With the increasing of waiting time, the ingot temperature decreases and the soaking time increases. This property is called deterioration. Setup time is needed between incompatible jobs. We show that if jobs have the same sizes, an optimal solution can be found within O(nlogn) time. If jobs have identical processing times, the problem is proved to be NP-hard in the strong sense. We propose an approximate algorithm whose absolute and asymptotic worst-case ratios are less than 2 and 11/9, respectively. When the jobs have arbitrary sizes and arbitrary processing times, the model is also NP-hard in the strong sense. An approximate algorithm with an absolute and asymptotic worst-case ratio less than 2 is proposed. The time complexity is O(nlogn).
Mathematics Subject Classification: 90B35
Key words: Batch processing / Optimization / Incompatible / Deterioration / Approximation algorithms
© The authors. Published by EDP Sciences, ROADEF, SMAI 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.