Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan
Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan
复制标题
DOI：
10.1016/j.ejor.2007.06.029
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
Jen-Shiang Chen
中科院分区：
文献类型：
--
作者：
Jen-Shiang Chen
本文研究了单机调度问题的周期性维护，机器被假定为定期停止维修的一个恒定的时间w在调度期间。同时，假设已经预先安排了维护周期[u，v]，并且假设时间w不超过可用维护周期[u，v]（即w <$v-u）。时间u（v）是机器开始（停止）其维护的最早（最晚）时间。目标是最小化最大完工时间。两个混合二进制整数规划（BIP）模型推导出最优解。此外，提出了一种有效的启发式算法，用于寻找大型问题的近似最优解。最后，通过算例验证了模型的有效性和算法的有效性。混合BIP模型可以最优地解决多达100个作业的实例，而启发式的平均百分比误差低于1%。
This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u,v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u,v] (i.e. w⩽v−u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.