Key Takeaways & Executive Findings
- •• Introduces an optimal polynomial-time algorithm for preemptive scheduling on uniform machines with non-simultaneous availability. • Derives a lower bound on the optimal makespan using a virtual machine transformation that ensures earlier-available machines have greater speeds. • Achieves time complexity O(nm + m^2), making it efficient for practical scheduling problems. • Limits the number of preemptions to at most 1/2(m^2 + 3m) - 2, balancing optimality with operational simplicity.
Abstract
We study preemptive scheduling on m uniform machines with non-simultaneous available times to minimize the makespan. Each machine has a different speed and a different available time. We first provide a lower bound on the optimal makespan of the problem by converting the real machines to virtual machines that guarantee a machine with an earlier available time having a greater speed at any time. Then, we provide an algorithm with time complexity of O(nm+m^2) to find an optimal schedule with, at most, 1/2(m^2+3m)-2 preemptions, where n is the number of jobs.
1. Introduction
In this paper, we consider the problem of preemptive scheduling on parallel machines with non-simultaneous machine-available times. Our goal is to minimize the maximum completion time, i.e., the makespan. Unlike classical parallel-machine scheduling where all the machines are available simultaneously at time zero, the machines in our problem may not be available at time zero. Lee (1991) first considered such a scheduling model, which has many applications in real industry settings (Lee et al., 1997); e.g., machines may require different setup times or warm-up times before they start processing jobs due to preventive maintenance and adjustment requirements.
We formally introduce the problem under study as follows: There are n independent jobs {J1, J2, …, Jn} to be processed on m parallel machines {M1, M2, …, Mm}. Each job Jj (j∈{1, 2, …, n}) has a processing time pj ( pj>0). Each machine Mi (i∈{1, 2, …, m}) has a speed si (si>0) and is available at time ri, which means that Mi can only start processing jobs at time ri. Without loss of generality, we assume that r1⩽r2⩽…⩽rm. Note that the processing time of job Jj is pj/si if it is processed on machine Mi. Job preemption is allowed. Using the three-field notation for scheduling problems, we denote our problem as Qm, ri|pmtn|Cmax.
Loading authentic research manuscript (Pages 1–5)...
Hao Zhou, Liping Cao, Qi Wei, Zhenyu Shu, Yiwei Jiang (2025). An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines. Frontiers of Information Technology & Electronic Engineering. https://doi.org/10.1631/FITEE_2300767
Research & Educational Purpose Only:The translations, structured abstracts, analytical annotations, and data reports provided by SinoTechIntel are intended exclusively for academic research, internal corporate R&D, and educational benchmarking. They do not constitute formal engineering, chemical safety, legal, or professional advice.
Copyright & Intellectual Property Notice: Original copyright of the underlying source articles and experimental data remains with the respective authors, institutions, and original publishing journals. SinoTechIntel claims intellectual property only over its proprietary translations, analytical syntheses, and AEO structured enhancements in accordance with international fair use and academic citation principles.
Frequently Asked Questions
What is the scheduling problem addressed in this paper?
The problem of preemptive scheduling on m uniform machines with non-simultaneous available times to minimize the makespan, denoted as Qm, ri|pmtn|Cmax.
What is the main contribution of the paper?
An optimal algorithm with time complexity O(nm+m^2) and a lower bound on the optimal makespan using virtual machines.
What is the maximum number of preemptions in the proposed schedule?
At most 1/2(m^2+3m)-2 preemptions.
How does the algorithm work in brief?
It converts real machines to virtual machines ensuring that earlier available machines have greater speeds, then finds an optimal schedule.
What is the significance of this work for real-world scheduling?
It provides an efficient optimal solution for scenarios where machines have different speeds and availability times, which is common in industrial settings.
Related Technical Papers & Translations
Design and optimization of a high-efficiency distillation process for cellulosic fuel ethanol integrated with thermal coupling and molecular sieve adsorption
To address the challenges of high energy consumption and prominent costs in the traditional three-columns distillation process for cellulosic fuel ethanol, a distillation—molecular sieve coupling separation process is proposed. This process integrates a three-column (crude distillation column, first distillation column, second distillation column) system with a 3A molecular sieve adsorption deep dehydration unit. A thermal coupling network is constructed via differential pressure design (steam from medium/high-pressure columns as mutual heat sources, reboiler liquid waste heat for feed preheating), and molecular sieve adsorption conditions are optimized. The study first performs a thermodynamic consistency test on the ethanol—water system, determines optimal non-random two-liquid (NRTL) model binary interaction parameters via experimental data regression for Aspen Plus simulation. Aiming at minimum total annual cost (TAC), Aspen Plus is used to optimize process parameters (theoretical tray number, feed location, reflux ratio, side-draw position, etc.). Economic analysis shows this process reduces CO2 emission costs by 27.56%, TAC by 15.58% (to 5.123 × 106 USD·a-1), and increases ethanol purity to ＞99.6%, providing an effective solution for green, efficient separation.
A cohesion loss model for determining residual strength of deep bedded sandstone
Rock residual strength, as an important input parameter, plays an indispensable role in proposing the reasonable and scientific scheme about stope design, underground tunnel excavation and stability evaluation of deep chambers. Therefore, previous residual strength models of rocks established were reviewed. And corresponding related problems were stated. Subsequently, starting from the effects of bedding and whole life-cycle evolution process, series of triaxial mechanical tests of deep bedded s
Federated model with contrastive learning and adaptive control variates for human activity recognition
Recent attention to privacy issues demands a communication-safe method for training human activity recognition (HAR) models on client activity data. Federated learning (FL) has become a compelling technique to facilitate model training between the server and clients while preserving data privacy. However, classical FL methods often assume independent and identically distributed (IID) data among clients. This assumption does not hold true in practical scenarios. Human activity in real-world scena