Multiprocessor scheduling with testing: improved online algorithms and numerical experiments

Mingyang Gong (), Jing Fan (), Guohui Lin (), Bing Su (), Zihan Su () and Xiang Zhang ()
Additional contact information
Mingyang Gong: University of Alberta
Jing Fan: University of Alberta
Guohui Lin: University of Alberta
Bing Su: Xi’an Technological University
Zihan Su: University of Alberta
Xiang Zhang: University of Alberta

Journal of Scheduling, 2025, vol. 28, issue 5, No 3, 513-527

Abstract: Abstract We investigate scheduling with testing in the multiprocessor environment. Scheduling with testing, disallowing job preemption, is a variant recently proposed by Dürr et al. and Albers et al. to model many real-life applications where the scheduler decides to either execute a job for a likely overestimated length of time, or test the job to obtain its exact processing time, followed by executing the job for the exact length of time on the same machine. We present an online algorithm with competitive ratio 2.8681, improving the previous best known guarantee of 2.9514; when every test operation takes one unit of time, we present an online algorithm with competitive ratio approaching 2.5276, improving the previous best known guarantee of 2.8081. Compared to the prior work, the novel design ideas in our algorithm for the general testing case are to set up multiple thresholds for job testing decision-making and to use multiple sorting/selection criteria to determine the job processing order. We also propose a way to construct a benchmark dataset from the one for the classic multiprocessor scheduling problem, and on this benchmark dataset we demonstrate the empirical performance of our algorithms against the prior algorithms.

Keywords: Scheduling; Multiprocessor; Scheduling with testing; Makespan; Online algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-025-00850-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:28:y:2025:i:5:d:10.1007_s10951-025-00850-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-025-00850-3

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().