A new composite heuristic to minimize the total tardiness for the single machine scheduling problem with variable and flexible maintenance
针对半导体行业中的单机调度与维护问题，提出了四种混合整数线性规划模型和一种新型复合启发式算法，通过实验对比验证了其有效性，帮助生产计划人员最小化总延误。
• We address single machine scheduling problem with flexible/variable maintenance. • We introduce three new MILP models. • We present a novel heuristic algorithm configured into three distinct variants. • We compare several heuristic algorithms. Inspired by a real-world maintenance/job scheduling issue coming from the semiconductor industry, the present paper proposes a new heuristic algorithm structure for the single machine scheduling T-problem with flexible and variable maintenance, job release dates and sequence dependence setup times. Considering the typical short-term production planning needs, a single maintenance problem has to be scheduled within a certain time interval, along with a set of jobs so as to minimize the total tardiness. A twofold contribution emerges from the present paper. First, four mixed-integer linear programming models are developed for the problem at hand and compared in terms of time to convergence and computational complexity. Second, a novel heuristic algorithm, which has been configured into three distinct variants, has been compared with 17 alternative heuristics from the relevant literature based on a comprehensive experimental campaign. The numerical results allow the selection of the most suitable MILP model and confirm the effectiveness of the proposed heuristic approach.