Minimising total weighted completion time for semi-online single machine scheduling with known arrivals and bounded processing times

Abstract

This paper addresses the semi-online scheduling problem of minimising the total weighted completion time on a single machine, where a combination of information on jobs release dates and processing times is considered. In this study, jobs can only arrive at known future times and a lower bound on jobs processing times is known in advance. A new semi-online algorithm is presented and is shown to be the best possible for the considered problem. In order to make this statement, a new lower bound on the competitive ratio of any semi-online algorithm for the problem is developed and, using competitive analysis, the proposed semi-online algorithm is shown to have a competitive ratio that matches the lower bound.

Keywords:

• Machine scheduling
• sem-online algorithm
• lower bounds
• total weighted completion time
• competitive analysis

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

The authors confirm that the data supporting the findings of this study are available within the article.

Additional information

Funding

This work has been conducted in the OTRIF project funded by the European Commission (FEDER funds).

Notes on contributors

Hajar Nouinou

Hajar Nouinou is an Associate Professor since 2022 at CESI Engineering School – Nancy Campus. She works in the CESI LINEACT – Digital Innovation Laboratory for Companies and Apprenticeships for the Competitiveness of Territories (UR 7527). She obtained her professional thesis in 2021 at the University of Technology of Troyes. She holds a master's degree in optimisation of industrial systems from the University of Lorraine and an engineering degree in Industrial Engineering and Logistics from the National School of Applied Sciences of Tangier. Her research topics concern modelling, performance evaluation and optimisation of production scheduling under uncertainty.

Taha Arbaoui

Taha Arbaoui holds an engineering degree in computer science from the Ecole nationale Superieure d'Informatique of Algiers and a PhD in computer science from the University of Technology of Compigne. Since 2015, he has been an Assistant Professor at the University of Technology of Troyes and a member of the Laboratory of Computer Science and Digital Society. He is also the Head of Industrial and Foreign Affairs of the Institute of Industries and Factories of the Future of Troyes (ISIFT). His research interests include developing optimisation approaches for large-scale problems in scheduling, planning, and timetabling in various applications fields, such as industry 4.0, energy and healthcare.

Alice Yalaoui

Alice Yalaoui obtained her engineering degree in industrial engineering from the University of Technology of Troyes in 2001, her master's degree (in 2001) and her PhD degree in system optimisation and security from the Troyes University of Technology (UTT) in 2004. She is currently Professor at Troyes University of Technology, in the Computer Science & Digital Society Laboratory (LIST3N). Her research topic focuses on the scheduling problems, system design, lot-sizing, operations research, modelling, analysis and optimisation of logistic and production systems, reliability and maintenance optimisation and on optimisation problems in general.