semi-online scheduling

Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part I: Tight Lower Bounds

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Approximation Algorithms Tags , , ,

    This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds $1$ and $s \geq 1$, so that the overall completion time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs arrive one … Read more

    New Lower Bounds for Semi-online Scheduling on Two Uniform Machines with Known Optimum

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Scheduling Tags , , ,

    This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds 1 and s ≥ 1, so that the overall finishing time, i.e. the makespan, is earliest possible. We consider a semi- online variant introduced (for equal speeds) by Azar and Regev, where the jobs are … Read more