Single‐machine scheduling problem with resource dependent release dates to minimise total resource‐consumption

Abstract

This article considers the single‐machine scheduling problem to minimise the total resource consumption under the constraint that the makespan does not exceed a given limit, in which the release date of a job is a linear decreasing continuous function of the resource consumption. This problem is NP-hard in the strong sense. We design a simulated annealing (SA) algorithm to obtain the near-optimal solution with high quality. Two operators, right-move and left-move, are defined and their influences on the resource consumption are analysed. We use two operations, insert and swap, to generate the neighbourhood, and discuss how to calculate the change of total resource consumption. To evaluate the performance of the proposed algorithm, we relax the problem to an assignment problem, and obtain a lower bound by the Hungary method. And then, we improve its quality by Chu's method. Based on the settings that Janiak provided, we generate the random test data in our experiments to simulate the ingot preheating and hot-rolling process in steel mills. The accuracy and efficiency of the proposed SA algorithm are tested based on those data with problem sizes varying from 50 to 200 jobs. The computational results indicate that the SA approach is promising and capable of solving large-scale problems in a reasonable time.

Keywords:

• scheduling
• single machine
• makespan
• resource allocation
• release dates

Acknowledgements

The authors would like thank the anonymous referees for their valuable comments and suggestions that helped improve this article. This work was supported by the fund from the National Natural Science Foundation of China under grant nos 70631003, 70871032, 90924021 and 70971035 and by the fund from the National 863 High-Tech Research and Development Program of China through approved no. 2008AA042901.