Group Scheduling With Nonperiodical Maintenance and Deteriorating Effects

[EN] In this paper, we consider single-machine group scheduling with nonperiodical maintenance and deteriorating effects. Nonperiodical maintenance, which has unfixed maintaining interval or the number of jobs in each group is unfixed, results in a variable number of groups. Deteriorating effects lead to longer processing times of which the deterioration index depends on job grouping. This problem is of significance in different production settings and is much more difficult than and general that other simpler single-machine group scheduling problems. Making use of historical processing times, we construct the actual processing time model for jobs. We prove that the problem under study is NP-hard. By transforming the optimization objective, properties are discovered and two batch-based heuristics are presented for small size problems. To further improve the effectiveness for large size problems, an iterated greedy algorithm is proposed being its main advantages simplicity and effectiveness. The proposed methods are evaluated over a large number of random instances with calibrated parameters and components. Comprehensive computational and statistical analyses demonstrate the superiority of the methods proposed over adapted existing approachesThis work was supported in part by the National Key Research and Development Program of China under Grant 2017YFB1400801, in part by the National Natural Science Foundation of China under Grant 61572127, Grant 61872077, and Grant 61832004, and in part by the Collaborative Innovation Center of Wireless Communications Technology. The work of R. Ruiz was supported by the Spanish Ministry of Economy and Competitiveness through the Project "SCHEYARD-Optimization of Scheduling Problems in Container Yards" with FEDER funds under Grant DPI2015-65895-R. This paper was recommended by Associate Editor W. ShenXu, H.; Li, X.; Ruiz García, R.; Zhu, H. (2021). Group Scheduling With Nonperiodical Maintenance and Deteriorating Effects. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 51(5):2860-2872. https://doi.org/10.1109/TSMC.2019.29174462860287251