Scheduling Problems with Bounded Processing or Setup Times

ALLAHVERDİ A.

Kuala, Lumpur, Malaysiam, 3rd International Multidisciplinary Conference on Education, Engineering and Social Sciences, Kuala-Lumpur, Malezya, 26 Kasım 2022 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1007/978-981-19-8152-4_15
  • Basıldığı Şehir: Kuala-Lumpur
  • Basıldığı Ülke: Malezya
  • Gazi Üniversitesi Adresli: Hayır

Özet

For the online hierarchical scheduling problem on two parallel machines, the objective is to maximize the minimum machine load. When the processing times are bounded by an interval [1, alpha], Luo and Xu [8] designed an optimal algorithm with a competitive ratio of 1 + alpha based on the threshold method. In this paper, we propose a simpler optimal online algorithm based on modified list scheduling.