IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i19p4034-d1245890.html
   My bibliography  Save this article

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

Author

Listed:
  • Matteo Avolio

    (Department of Mathematics and Computer Science, University of Calabria, 87036 Rende, Italy)

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.

Suggested Citation

  • Matteo Avolio, 2023. "Balancing the Average Weighted Completion Times in Large-Scale Two-Agent Scheduling Problems: An Evolutionary-Type Computational Study," Mathematics, MDPI, vol. 11(19), pages 1-15, September.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:19:p:4034-:d:1245890
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/19/4034/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/19/4034/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    2. Agnetis, Alessandro & Chen, Bo & Nicosia, Gaia & Pacifici, Andrea, 2019. "Price of fairness in two-agent single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 276(1), pages 79-87.
    3. Allesandro Agnetis & Pitu B. Mirchandani & Dario Pacciarelli & Andrea Pacifici, 2004. "Scheduling Problems with Two Competing Agents," Operations Research, INFORMS, vol. 52(2), pages 229-242, April.
    4. Fred Glover, 1975. "Improved Linear Integer Programming Formulations of Nonlinear Integer Problems," Management Science, INFORMS, vol. 22(4), pages 455-460, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gudmundsson, Jens & Hougaard, Jens Leth & Platz, Trine Tornøe, 2023. "Decentralized task coordination," European Journal of Operational Research, Elsevier, vol. 304(2), pages 851-864.
    2. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    3. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    4. Zhang, Xingong, 2021. "Two competitive agents to minimize the weighted total late work and the total completion time," Applied Mathematics and Computation, Elsevier, vol. 406(C).
    5. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    6. Byung-Cheon Choi & Myoung-Ju Park, 2015. "A Batch Scheduling Problem with Two Agents," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-19, December.
    7. Yokoyama, Ryohei & Kitano, Hiroyuki & Wakui, Tetsuya, 2017. "Optimal operation of heat supply systems with piping network," Energy, Elsevier, vol. 137(C), pages 888-897.
    8. Tian, Xueyu & You, Fengqi, 2019. "Carbon-neutral hybrid energy systems with deep water source cooling, biomass heating, and geothermal heat and power," Applied Energy, Elsevier, vol. 250(C), pages 413-432.
    9. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    10. Longinidis, Pantelis & Georgiadis, Michael C., 2014. "Integration of sale and leaseback in the optimal design of supply chain networks," Omega, Elsevier, vol. 47(C), pages 73-89.
    11. Rostami, Borzou & Chassein, André & Hopf, Michael & Frey, Davide & Buchheim, Christoph & Malucelli, Federico & Goerigk, Marc, 2018. "The quadratic shortest path problem: complexity, approximability, and solution methods," European Journal of Operational Research, Elsevier, vol. 268(2), pages 473-485.
    12. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    13. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.
    14. Wen-Hung Wu & Yunqiang Yin & T C E Cheng & Win-Chin Lin & Juei-Chao Chen & Shin-Yi Luo & Chin-Chia Wu, 2017. "A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 111-120, February.
    15. Unai Aldasoro & María Merino & Gloria Pérez, 2019. "Time consistent expected mean-variance in multistage stochastic quadratic optimization: a model and a matheuristic," Annals of Operations Research, Springer, vol. 280(1), pages 151-187, September.
    16. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    17. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    18. Christodoulos Floudas & Xiaoxia Lin, 2005. "Mixed Integer Linear Programming in Process Scheduling: Modeling, Algorithms, and Applications," Annals of Operations Research, Springer, vol. 139(1), pages 131-162, October.
    19. Gupta, Renu & Bandopadhyaya, Lakshmisree & Puri, M. C., 1996. "Ranking in quadratic integer programming problems," European Journal of Operational Research, Elsevier, vol. 95(1), pages 231-236, November.
    20. Angel L. Cedeño & Reinier López Ahuar & José Rojas & Gonzalo Carvajal & César Silva & Juan C. Agüero, 2022. "Model Predictive Control for Photovoltaic Plants with Non-Ideal Energy Storage Using Mixed Integer Linear Programming," Energies, MDPI, vol. 15(17), pages 1-21, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:19:p:4034-:d:1245890. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.