Journal of shanghai Jiaotong University (Science) ›› 2016, Vol. 21 ›› Issue (1): 112-120.doi: 10.1007/s12204-015-1690-z

Previous Articles     Next Articles

Heuristics for the Identical Machine Scheduling Problem with Preventive Maintenances

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)
  2. (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

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

摘要: 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

CLC Number: