Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan |
| |
Authors: | Jen-Shiang Chen |
| |
Institution: | Department of Management Information System, Far East University, 49 Junghua Road, Shinshr Shiang, Tainan 744, Taiwan, ROC |
| |
Abstract: | 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%. |
| |
Keywords: | Scheduling Single machine Maintenance Availability constraints Integer programming Heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|