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.
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
Notes on contributors
![](/cms/asset/dd4963d0-a42a-4bb3-a934-aea6c32b72b2/tprs_a_2217294_ilg0001.gif)
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.
![](/cms/asset/c92ef63b-820f-4c14-a7a7-df055e686f12/tprs_a_2217294_ilg0002.gif)
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.
![](/cms/asset/1666ac98-94cd-44cf-855c-ae6c4ade32e5/tprs_a_2217294_ilg0003.gif)
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.