Balancing the Average Weighted Completion Times in Large-Scale Two-Agent Scheduling Problems: An Evolutionary-Type Computational Study

Matteo Avolio ()
Additional contact information
Matteo Avolio: Department of Mathematics and Computer Science, University of Calabria, 87036 Rende, Italy

Mathematics, 2023, vol. 11, issue 19, 1-15

Abstract: The problem of balancing the average weighted completion times of two classes of jobs is an NP-hard scheduling problem that was very recently introduced in the literature. Interpreted as a cooperative-type two-agent single-machine problem, its applications are in various practical contexts such as in logistics for balancing the delivery times, in manufacturing for balancing the assembly lines and in services for balancing the waiting times of groups of people. The only solution technique currently existing in the literature is a Lagrangian heuristic, based on solving a finite number of successive linear assignment problems, whose dimension depends on the total number of jobs. Since the Lagrangian approach has not appeared to be particularly suitable for solving large-scale problems, to overcome this drawback, we propose to face the problem by means of a genetic algorithm. Differently from the Lagrangian heuristic, our approach is found to be effective also for large instances (up to 2000 jobs), as confirmed by numerical experiments.

Keywords: scheduling; multi-agent; genetic algorithm; large scale; local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/19/4034/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/19/4034/ (text/html)

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:gam:jmathe:v:11:y:2023:i:19:p:4034-:d:1245890

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().