Minimising total weighted completion time for semi-online single machine scheduling with known arrivals and bounded processing times
Authors : Hajar Nouinou (LINEACT), Taha Arbaoui (LIST3N), Alice Yalaoui (LIST3N)
Article : Articles dans des revues internationales ou nationales avec comité de lecture - 31/05/2023 - INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
This paper addresses the semi-online scheduling problem of minimising the total weighted com pletion 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.