Back to Search
Start Over
Scheduling with Testing on Multiple Identical Parallel Machines
- Source :
- Lecture Notes in Computer Science ISBN: 9783030835071, WADS
- Publication Year :
- 2021
- Publisher :
- Springer International Publishing, 2021.
-
Abstract
- Scheduling with testing is a recent online problem within the framework of explorable uncertainty motivated by environments where some preliminary action can influence the duration of a task. Jobs have an unknown processing time that can be explored by running a test. Alternatively, jobs can be executed for the duration of a given upper limit. We consider this problem within the setting of multiple identical parallel machines and present competitive deterministic algorithms and lower bounds for the objective of minimizing the makespan of the schedule. In the non-preemptive setting, we present the SBS algorithm whose competitive ratio approaches 3.1016 if the number of machines becomes large. We compare this result with a simple greedy strategy and a lower bound which approaches 2. In the case of uniform testing times, we can improve the SBS algorithm to be 3-competitive. For the preemptive case we provide a 2-competitive algorithm and a tight lower bound which approaches the same value.
- Subjects :
- Schedule
Mathematical optimization
021103 operations research
Job shop scheduling
Competitive analysis
Computer science
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Upper and lower bounds
Scheduling (computing)
Task (project management)
010201 computation theory & mathematics
Limit (mathematics)
Duration (project management)
Subjects
Details
- ISBN :
- 978-3-030-83507-1
- ISBNs :
- 9783030835071
- Database :
- OpenAIRE
- Journal :
- Lecture Notes in Computer Science ISBN: 9783030835071, WADS
- Accession number :
- edsair.doi...........710a67935000bf63143971032e7d4035