A Novel Time-Indexed Model for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times

Abstract

In this thesis, we address time-indexed models for the single machine scheduling problem with sequence-dependent setup times. While the ideal formulation of the machines capacity constraint is known in the absence of setup times, no such formulation has been identified when sequence-dependent setup times are present. To address the computational burden caused by the large size of time-indexed models, it is essential to formulate the capacity constraint using a small number of strong constraints. To this end, we propose a two-phase algorithm for formulating the capacity constraint. The first phase reduces the number of constraints in the time-indexed model, while the second phase constructs constraints to tighten the linear programming (LP) relaxation bound. Computational experiments demonstrate that the resulting novel time-indexed model significantly outperforms existing models in the literature, achieving much tighter LP relaxation bounds with a considerably smaller model size and in shorter solving times. Additionally, we introduce a restricted time-indexed model that can be applied when only a subset of the decision variables is used. This model further reduces its size by identifying constraints that can be excluded while maintaining the models validity. Computational results confirm that the restricted model effectively reduces the number of constraints.

본 논문에서는 순서 의존적 작업준비시간을 가지는 단일 기계 일정계획 문제를 푸는 시간인덱스 모형을 다룬다. 작업준비시간이 없는 경우에는 설비의 용량 제약에 대한 이상적인 모형화가 알려져 있는데, 순서 의존적 작업준비시간이 존재하는 경우에는 이러한 모형화가 아직 알려져 있지 않다. 시간-인덱스 모형의 큰 크기로 인한 계산 부담을 해결하기 위해서는 적은 수의 강한 제약식들로 설비의 용량 제약을 모형화하는 것이 필수적이다. 이를 위해 용량 제약을 모형화하기 위한 두 단계 알고리즘을 제안한다. 첫 번째 단계에서 는 시간-인덱스 모형에 포함될 제약식 수를 줄이고, 두 번째 단계에서는 모형의 선형완화경계 값을 강화시키기 위한 제약식들을 구축한다. 계산 실험을 통해 제안된 새로운 시간-인덱스 모형이 기존 문헌의 모형들보다 훨씬 더 작은 모델 크기를 가지며 훨씬 더 좋은 선형완화경계 값을 더 빠르게 얻을 수 있음을 확인하였다. 추가적으로, 결정 변수의 부분 집합만을 사용할 때 적용 가능한 제한된 시간-인덱스 모형을 소개한다. 이 모형은 모형의 유효성을 유지하면서 제외할 수 있는 제약식을 식별하여 모형의 크기를 더욱 줄인다. 이 제한된 모형이 제약식의 수를 효과적으로 줄임을 실험적으로 확인하였다.