계단형 향상 작업을 갖는 단일설비 스케줄링을 위한 분기한정 알고리즘
Branch and Bound Algorithm for Single Machine Scheduling with Step-Improving Jobs
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (11)
- Berlinska, J., "Scheduling for Data Gathering Networks with Data Compression", European Journal of Operational Research, 246(3), pp.744~749 (2015)
- Cheng, T., "Single Machine Scheduling with Step-deteriorating Processing Times", European Journal of Operational Research, 134(3), pp.623~630 (2001)
- Cheng, T., "Scheduling with Step-improving Processing Times", Operations Research Letters, 34(1), pp.37~40 (2006)
- Gawiejnowicz, S., "A Review of Four Decades of Time-dependent Scheduling: Main Results, New Topics, and Open Problems", Journal of Scheduling, 23(1), pp.3~47 (2020)
- Ji, M., "A Simple Linear Time Algorithm for Scheduling with Step-improving Processing Times", Computers & Operations Research, 34(8), pp.2396~2402 (2007)
- Scheduling of Step-improving Jobs with Multiple Critical dates, "Kim, E. -S.", ~ (2023)
- Kim, E. -S., "Minimizing Total Completion Time on a Single Machine with Step Improving Jobs", Journal of the Operational Research Society, 66(9), pp.1481~1490 (2015)
- Kim, H. -J., "Scheduling of Step-improving Jobs with an Identical Improving Rate", Journal of the Operational Research Society, 73(5), pp.1127~1136 (2022)
- Li, K., "Parallel Machine Scheduling with Position-based Deterioration and Learning Effects in an Uncertain Manufacturing System", Computers & Industrial Engineering, 149, pp.1~12 (2020)
- Luo, W., "Communication Scheduling in Data Gathering Networks of Heterogeneous Sensors with Data Compression : Algorithms and Empirical Experiments", European Journal of Operational Research, 271(2), pp.462~473 (2018)
- Sundararaghavan, P. S., "Single Machine Scheduling with Start Time Dependent Processing Times : Some Solvable Cases", European Journal of Operational Research, 78(3), pp.394~403 (1994)