Title: New conditions of dominance and optimality for single-machine scheduling problems with nested execution intervals

Authors: Samia Ourari; Farouk Yalaoui

Addresses: Faculty of Technology, M'Hamed Bougara University of Boumerdès, Cité Frantz Fanon, Boumerdes, 35000, Algeria; Advanced Technologies Development Centre (CDTA), Cité, 20 Août 1956, Baba Hassen 16081, Algeria ' LIST3N, University of Technology of Troyes, 12 rue Marie Curie, Troyes Cedex, France

Abstract: In this paper, we consider the problem of scheduling a set of n + 1 jobs on a single disjunctive machine. Each job has a fixed processing time and a temporal execution interval. Pre-emption is not allowed. Temporal execution intervals are assumed to have a perfect pyramidal structure, i.e., the execution intervals of the jobs are nested within each other, or none two of them are contained within each other. The objective is to find a feasible sequence that minimises the maximum lateness under some particular constraints. In order to do so, new dominance properties under known necessary and sufficient conditions are established, and optimality conditions of certain job sequences are given.

Keywords: single-machine scheduling; nested or perfect intervals; dominance conditions; optimality condition; scheduling rules.

DOI: 10.1504/IJMOR.2024.142135

International Journal of Mathematics in Operational Research, 2024 Vol.29 No.2, pp.191 - 213

Received: 28 Mar 2023
Accepted: 02 Apr 2023
Published online: 08 Oct 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article