Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization

Tifenn Rault (), Faiza Sadi, Jean-Charles Billaut () and Ameur Soukhal ()
Additional contact information
Tifenn Rault: Université François Rabelais de Tours, CNRS
Faiza Sadi: Université François Rabelais de Tours, CNRS
Jean-Charles Billaut: Université François Rabelais de Tours, CNRS
Ameur Soukhal: Université François Rabelais de Tours, CNRS

Journal of Scheduling, 2024, vol. 27, issue 5, No 5, 485-505

Abstract: Abstract We consider a two-agent scheduling problem with interfering job sets. Agent A—which can be considered as the resource manager—is associated with the whole set of jobs, and agent B—which can be considered as an application master—is associated with a subset of jobs. Each agent aims at minimizing either the maximum or the total completion time of its jobs. Considering an identical parallel machines environment, the goal is to find an assignment and a schedule of jobs which represents the best compromise between the requirements of the agents. The class of multi-agent scheduling problems has drawn a significant interest to researchers in the area of scheduling and operational research. When both agents minimize the makespan, we prove that the number of Pareto solutions is bounded and we show that this bound is reached. Using the $$\varepsilon $$ ε -constraint approach, we propose two integer programming formulations that allow to obtain the exact Pareto front for each problem. Given that the studied problems are NP-hard, we propose genetic algorithms (NSGA-II) to generate approximated Pareto fronts. Computational experiments are conducted to analyze the performances of the proposed methods. The results indicate that the genetic algorithms provide high-quality Pareto fronts and are computationally efficient.

Keywords: Multi-agent scheduling; Parallel machines; Pareto front; Genetic algorithms; Integer programming (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-024-00812-1 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:27:y:2024:i:5:d:10.1007_s10951-024-00812-1

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

DOI: 10.1007/s10951-024-00812-1

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 ().