긴급주문과 순서의존준비시간이 있는 흐름공정의 일정계획 휴리스틱 알고리즘 연구

This paper considers a two-machine flowshop scheduling problem in which there are sequence-dependent setup times and two classes of jobs with different urgencies, i.e., urgent jobs and normal (not urgent) jobs. The objective of this problem is minimizing total tardiness of one class for urgent jobs and the maximum completion time (makespan) of the other class for normal (non-urgent) jobs. To solve this problem, we propose a mathematical formulation and several heuristic algorithms (three list scheduling algorithms, two constructive algorithms, one meta-heuristic algorithm). To evaluate the performance of the developed algorithms, computational experiments are performed on randomly generated instances. The results show that the proposed algorithms can provide reasonable solutions in a short time for given instances.