On the minimum number of resources for a perfect schedule. (English) Zbl 07700326
Summary: In 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\) or \(B=4\) resources are sufficient for a perfect schedule.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
minimizing the number of resources; perfect schedule; single-processor scheduling; mixed integer linear programmingReferences:
| [1] | Benmansour, R.; Braun, O.; Hanafi, S., The single processor scheduling problem with time restrictions: complexity and related problems, J Sched, 22, 465-471 (2018) · Zbl 1442.90067 · doi:10.1007/s10951-018-0579-8 |
| [2] | Benmansour, R.; Braun, O.; Hanafi, S.; Mladenovic, N., Using a variable neighborhood search to solve the single processor scheduling problem with time restrictions, Lect Notes Comput Sci, 11328, 202-215 (2019) · doi:10.1007/978-3-030-15843-9_16 |
| [3] | Braun, O.; Chung, F.; Graham, R., Single-processor scheduling with time restrictions, J Sched, 17, 399-403 (2014) · Zbl 1305.68041 · doi:10.1007/s10951-013-0342-0 |
| [4] | Braun, O.; Chung, F.; Graham, R., Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions, OR Spectrum, 38, 531-540 (2016) · Zbl 1339.90128 · doi:10.1007/s00291-016-0431-5 |
| [5] | Kravchenko, SA; Werner, F., Parallel machine scheduling problems with a single server, Math Comput Model, 26, 1-11 (1997) · Zbl 1185.90082 · doi:10.1016/S0895-7177(97)00236-7 |
| [6] | Rustogi, K.; Strusevich, VA, Parallel machine scheduling: impact of adding extra machines, Oper Res, 61, 1243-1257 (2013) · Zbl 1291.90100 · doi:10.1287/opre.2013.1208 |
| [7] | 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 |
| [8] | Zhang, A.; Chen, Y.; Chen, L.; Chen, G., On the NP-hardness of scheduling with time restrictions, Discret Optim, 28, 54-62 (2017) · Zbl 1462.90054 · doi:10.1016/j.disopt.2017.12.001 |
| [9] | Zhang, A.; Ye, F.; Chen, Y.; Chen, G., Better permutations for the single-processor scheduling with time restrictions, Optim Lett, 11, 715-724 (2017) · Zbl 1367.90057 · doi:10.1007/s11590-016-1038-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
