New controllable processing time scheduling with subcontracting strategy for no-wait job shop problem
研究了无等待作业车间调度问题，加入截止日期和外包成本约束，提出两种混合整数线性规划模型和一种滚动时间线人工蜂群算法，用于求解小规模最优解和大规模高质量解。
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.