On the minimum number of resources for a perfect schedule

Central European Journal of Operations Research - Tập 31 Số 1 - Trang 191-204 - 2023
Rachid Benmansour1, Oliver Braun2
1SI2M Laboratory, Institut National de Statistique et d’Économie Appliquée, Rabat, Morocco
2Trier University of Applied Sciences, Environmental Campus Birkenfeld, 55768, Birkenfeld, Germany

Tóm tắt

AbstractIn the single-processor scheduling problem with time restrictions there is one main processor and B resources that are used to execute the jobs. A perfect schedule has no idle times or gaps on the main processor and the makespan is therefore equal to the sum of the processing times. In general, more resources result in smaller makespans, and as it is in practical applications often more economic not to mobilize resources that will be unnecessary and expensive, we investigate in this paper the problem to find the smallest number B of resources that make a perfect schedule possible. We show that the decision version of this problem is NP-complete, derive new structural properties of perfect schedules, and we describe a Mixed Integer Linear Programming (MIP) formulation to solve the problem. A large number of computational tests show that (for our randomly chosen problem instances) only $$B=3$$ B = 3 or $$B=4$$ B = 4 resources are sufficient for a perfect schedule.

Từ khóa


Tài liệu tham khảo

Benmansour R, Braun O, Hanafi S (2018) The single processor scheduling problem with time restrictions: complexity and related problems. J Sched 22:465–471

Benmansour R, Braun O, Hanafi S, Mladenovic N (2019) Using a variable neighborhood search to solve the single processor scheduling problem with time restrictions. Lect Notes Comput Sci 11328:202–215

Braun O, Chung F, Graham R (2014) Single-processor scheduling with time restrictions. J Sched 17:399–403

Braun O, Chung F, Graham R (2016) Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum 38:531–540

Kravchenko SA, Werner F (1997) Parallel machine scheduling problems with a single server. Math Comput Model 26:1–11

Rustogi K, Strusevich VA (2013) Parallel machine scheduling: impact of adding extra machines. Oper Res 61:1243–1257

Ruiz R, Vallada E, Fernández-Martínez C (2009) Scheduling in flowshops with no-idle machines. In: Uday KC (ed) Computational intelligence in flow shop and job shop scheduling. Springer, Berlin, pp 21–51

Zhang A, Chen Y, Chen L, Chen G (2017) On the NP-hardness of scheduling with time restrictions. Discret Optim 28:54–62

Zhang A, Ye F, Chen Y, Chen G (2017) Better permutations for the single-processor scheduling with time restrictions. Optim Lett 11:715–724

Thông tin
Thông tin xuất bản

Central European Journal of Operations Research

Tập 31 Số 1

191-204

Thông tin tác giả