Single‐machine scheduling problem with flexible maintenance and non‐resumable jobs to minimise makespan. Issue 4 (23rd November 2020)

• Record Type: Journal Article
• Authors: Chen, Yarong; Huang, Chenjun; Chou, Fuh‐Der; Huang, Shenquan
• Is Part Of: IET collaborative intelligent manufacturing. Volume 2:Issue 4(2020)
• Page Start: 174
• Page End: 181
• Publication Date: 2020-11-23
• Subjects: single machine scheduling -- computational complexity -- minimisation -- combinatorial mathematics -- preventive maintenance -- job shop scheduling -- integer programming; flexible maintenance -- nonresumable jobs -- single‐machine scheduling problem -- high‐speed heuristic algorithms -- makespan minimisation -- preventive maintenance -- nondeterministic polynomial‐hard combinatorial optimisation problem -- mixed‐integer programming model -- MIP model -- branch‐and‐bound algorithm -- B&B algorithm -- near‐optimal solution -- minimum waste and lower bound index; Production management -- Periodicals; Production engineering -- Periodicals; Production management; Production engineering; Electronic journals; Periodicals; 658.5
• DOI: 10.1049/iet-cim.2020.0014
• Languages: English
• ISSNs: 2516-8398

Abstract

Abstract : Single‐machine scheduling problem with preventive maintenance is an non‐deterministic polynomial‐hard combinatorial optimisation problem, which has significant applications in the real world. To meet the realistic requirements, high‐speed heuristic algorithms should be developed. In this study, a single‐machine scheduling problem with flexible maintenance and non‐resumable jobs is studied. Some properties for optimally solving this problem are first proposed, and then two mixed‐integer programming (MIP) models are provided. Next, a branch‐and‐bound (B&B) algorithm, four heuristic algorithms and the procedures to improve the quality of their solution are developed based on the properties of the optimal solution. Experimental results indicate that the proposed heuristic algorithms can obtain near‐optimal solutions within a very short computation time compared with the MIP and B&B methods. The heuristic algorithms of Minimum Waste and Lower Bound Index are particularly satisfactory in terms of both solution efficiency and accuracy in solving the addressed problem.