We examine a single machine scheduling problem with step-improving jobs in which job processing times decrease step-wisely over time according to their starting times. The objective is to minimize total completion time which is defined as the sum of completion times of jobs. The total completion time is frequently considered as an objective because it is highly related to the total time spent by jobs in the system as well as work-in-progress. Many applications of this problem can be observed in the real world such as data gathering networks, system upgrades or technological shock, and production lines operated with part-time workers in each shift. Our goal is to develop a scheduling algorithm that can provide an optimal solution. For this, we present an efficient branch and bound algorithm with an assignment-based node design and tight lower bounds that can prune branch and bound nodes at early stages and accordingly reduce the computation time. In numerical experiments well designed to consider various scenarios, it is shown that the proposed algorithm outperforms the existing method and can solve practical problems within reasonable computation time.

1. 서 론
2. 문제정의 및 혼합정수계획모형
3. 분기한정 알고리즘
    3.1 노드 정의
    3.2 초기 목적식 값 상한(UB)
    3.3 노드의 목적식 값 하한(LB)
    3.4 알고리즘
4. 계산실험
    4.1 실험환경 및 디자인
    4.2 실험결과
5. 결론
Acknowledgments
References

• Jun-Ho Lee(School of Business, Chungnam National University) | 이준호 (충남대학교 경상대학 경영학부) Corresponding author