上海交通大学学报（英文版） ›› 2016, Vol. 21 ›› Issue (1): 112-120.doi: 10.1007/s12204-015-1690-z

• • 上一篇    下一篇

Heuristics for the Identical Machine Scheduling Problem with Preventive Maintenances

JIANG Cailin1 (江才林), LU Zhiqiang1* (陆志强), CUI Weiwei2 (崔维伟)   

  1. (1. Institute of Industrial Engineering, Tongji University, Shanghai 201804, China; 2. Department of Industrial Engineering and Logistics Management, Shanghai Jiaotong University, Shanghai 200240, China)
  • 出版日期:2016-02-29 发布日期:2016-03-21
  • 通讯作者: LU Zhiqiang (陆志强) E-mail:zhiqianglu@tongji.edu.cn

Heuristics for the Identical Machine Scheduling Problem with Preventive Maintenances

JIANG Cailin1 (江才林), LU Zhiqiang1* (陆志强), CUI Weiwei2 (崔维伟)   

  1. (1. Institute of Industrial Engineering, Tongji University, Shanghai 201804, China; 2. Department of Industrial Engineering and Logistics Management, Shanghai Jiaotong University, Shanghai 200240, China)
  • Online:2016-02-29 Published:2016-03-21
  • Contact: LU Zhiqiang (陆志强) E-mail:zhiqianglu@tongji.edu.cn

摘要： In this paper, two mixed integer programming models integrating production scheduling and preventive maintenances are proposed to derive the optimal solutions for the identical machine scheduling problem with unavailability constraints. In the first model, the maintenance activities are performed periodically and the objective is to minimize the makespan. In the second model, the maintenance activities are flexible and the machines’ continuous working time cannot exceed a maximum allowed time T; the objective is to minimize the total completion time of jobs. For the first problem, we propose a heuristic longest batch time (LBT) and prove that the worst case error bound of LBT is 2. For the second problem, we develop a heuristic modified smallest processing time (MSPT) based on some properties of the optimal solutions. Computational experiments show that both of the heuristics are effective and efficient compared with the results obtained by CPLEX and the other algorithms.

关键词: identical machine scheduling, unavailability constraints, heuristic

Abstract: In this paper, two mixed integer programming models integrating production scheduling and preventive maintenances are proposed to derive the optimal solutions for the identical machine scheduling problem with unavailability constraints. In the first model, the maintenance activities are performed periodically and the objective is to minimize the makespan. In the second model, the maintenance activities are flexible and the machines’ continuous working time cannot exceed a maximum allowed time T; the objective is to minimize the total completion time of jobs. For the first problem, we propose a heuristic longest batch time (LBT) and prove that the worst case error bound of LBT is 2. For the second problem, we develop a heuristic modified smallest processing time (MSPT) based on some properties of the optimal solutions. Computational experiments show that both of the heuristics are effective and efficient compared with the results obtained by CPLEX and the other algorithms.

Key words: identical machine scheduling, unavailability constraints, heuristic

中图分类号: