Die Kraft von Restarts in Online-Scheduling

• Antragsteller: Professor Dr. Rob van Stee
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2021 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 451155613

• Erstellungsjahr: 2025

Zusammenfassung der Projektergebnisse

In practice, (optimization) problems often have to be solved without complete knowledge. For example, in businesses, it is common for product orders to arrive throughout the day. Employees and machines therefore have to start processing before all orders are known and before the workday ends. This situation can be modeled by online problems. An online problem is characterized by the fact that the input arrives step by step and must be processed in the given order without knowledge of the upcoming input. An online algorithm is a set of rules that determines how this processing takes place. In this project, we dealt with online scheduling. Tasks (jobs) of different sizes arrive online and must be processed on a single machine. The goal is to minimize the average completion time. In principle, jobs should be processed in order from smallest to largest. If it is possible to interrupt jobs and resume them later, it is even possible to achieve an optimal solution online by always running the job with the smallest remaining processing time (Shortest Remaining Processing Time, SRPT). But what happens if an interrupted job cannot be resumed where it left off, but must instead be restarted from the beginning? How good can an online algorithm be under these conditions? In this project, we developed a 1.465-competitive algorithm. This algorithm is relatively simple and, for each newly arriving job, considers the relative completion time (rct) — that is, the ratio between the completion time if the job is executed after the current job and the completion time if it is started immediately. If the rct is greater than 1.465, the current job is interrupted. This problem turned out to be surprisingly difficult, which is why we did not fully achieve the results we had hoped for. However, we are convinced that better online algorithms are possible, and this topic remains an exciting field of research. In addition, we studied the problem of minimizing the weighted maximum completion time on a single machine (also called the weighted makespan). For this problem, we developed an improved online algorithm with restarts and showed how, for the offline version of the problem (where the entire input is known at the beginning), the optimal solution can be approximated arbitrarily closely in an efficient way.

Projektbezogene Publikationen (Auswahl)

• SIGACT News Online Algorithms Column 40. ACM SIGACT News, 54(1), 90-104.
  Amouzandeh, Aflatoun; Schmitt, Soren & van Stee, Rob
  
• SIGACT News Online Algorithms Column 41: 2023 in review. ACM SIGACT News, 54(4), 108-125.
  Amouzandeh, Aflatoun; Schmitt, Sören & van Stee, Rob
  
• SIGACT News Online Algorithms Column 43: 2024 in review. ACM SIGACT News, 55(4), 94-107.
  Amouzandeh, Aflatoun; Schmitt, Sören & van Stee, Rob
  
• Improved Online Scheduling with Restarts on a Single Machine. Theory of Computing Systems, 70(1).
  Amouzandeh, Aflatoun & van Stee, Rob