시간 제약과 순서 의존 준비시간이 있는 흐름 공정에서의총 납기지연 최소화

This study considers a two-machine flowshop scheduling problem for the objective of minimizing total tardiness. In the flowshop, jobs have to be started on the second machine within the limited waiting time after those jobs are completed on the first machine, which is called a limited waiting time constraint, and jobs require sequence-dependent setup times before processing on the second machine. This scheduling problem is modeled in a mathematical programming formulation and the optimal solutions are obtained by CPLEX 12.9. However, solving this problem to optimality by using CPLEX needs a significantly long computation time since this problem is known to be NP-complete, hence heuristic algorithms are proposed to solve the problem within a short computation time. Computational experiments on randomly generated problem instances are done to evaluate the performance of the proposed algorithms and the results are reported.