z-logo
open-access-imgOpen Access
Single‐machine scheduling problem with flexible maintenance and non‐resumable jobs to minimise makespan
Author(s) -
Chen Yarong,
Huang Chenjun,
Chou FuhDer,
Huang Shenquan
Publication year - 2020
Publication title -
iet collaborative intelligent manufacturing
Language(s) - English
Resource type - Journals
ISSN - 2516-8398
DOI - 10.1049/iet-cim.2020.0014
Subject(s) - job shop scheduling , mathematical optimization , scheduling (production processes) , computer science , integer programming , heuristic , computation , branch and bound , upper and lower bounds , algorithm , mathematics , routing (electronic design automation) , computer network , mathematical analysis
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here