New controllable processing time scheduling with subcontracting strategy for no-wait job shop problem
Jinsheng Gao, Xiaomin Zhu, Kaiyuan Bai, Runtong Zhang
Abstract
This paper addresses the no-wait job shop scheduling problem with due date and subcontracting cost constraints. For the no-wait job shop problem, it does not allow for waiting or interruption between any two consecutive operations of the same job. Considering the deadline and controllable processing time requirements in the real world, due date and subcontracting cost constraints are integrated into the problem as a new extension. The problem has two objectives which are associated with makespan and subcontracting cost. The extended problem focuses on a special case that some jobs cannot satisfy their deadlines no matter how they are scheduled. To satisfy the deadlines, a subcontracting strategy, i.e. buying semi-finished products for processing, is put forward. Two mathematical models are proposed. One is an integrated MILP (MILP-IS), and the other is a rolling time line MILP (MILP-RTL). According to the idea of rolling time line, an artificial bee colony algorithm based on rolling time line (RTL-ABC) is developed. Comprehensive computational analysis is carried out. For small size problems, the optimal solutions are obtained by using these two mathematical models. For large size problems, RTL-ABC is able to find good-quality solutions in a reasonable time and improves the best-found solutions.