Operations Research 2025
Abstract Submission

2321. Scheduling on uniform processors with fixed jobs

Invited abstract in session TC-3: Maintenance Scheduling, stream Project Management and Scheduling.

Thursday, 11:45-13:15
Room: H5

Authors (first author is the speaker)

1. Liliana Grigoriu
Department of Control and Computers, National University of Science and Technology Politehnica Bucharest

Abstract

We consider the problem of nonpreemptive scheduling on uniformly related machines with fixed jobs, that is, jobs that need to perform on certain machines at given times, with the aim of minimizing the maximum completion time. Fixed jobs may also represent periods where the machines become unavailable due to scheduled maintenance, or even personnel breaks. In the context of scheduling with fixed jobs, the maximum completion time of a schedule can not occur before the latest end of a fixed job. We present a polynomial algorithm, the schedules of which end within 1.5 times the maximum completion time when there is at most one fixed job on each machine. Even for same-speed processors, it is NP-hard obtain schedules that obey better bounds for this problem. Like MULTIFIT, our algorithm uses binary search to find a deadline for which a feasible schedule can be generated by using the First Fit Decreasing(FFD) algorithm to schedule the jobs in the available time intervals on machines, which are delimited by the fixed jobs, the start of the schedule, and the chosen deadline. Before attempting to schedule the jobs by using FFD, our algorithm orders these time intervals in nondecreasing order of their length, which we define to be the duration of the time interval times the speed factor of the machine on which it occurs. We present experimental results with regard to the performance of this algorithm. For example, for the special case when there is one fixed job on each machine, with machine speeds between 1 and 10, 100 randomly generated instances with 10 machines and an average of 30 jobs per machine have an average error below 0.1%, whereas 100 randomly generated instances with 5 processors and an average of 10 jobs per machine have a worst observed error below 0.9%.

Keywords

Status: accepted

Back to the list of papers