Semi-online scheduling on two identical machines with a common due date to maximize total early work
| Autor: | Isabelle Chalamon, Malgorzata Sterna, Youqing Liu, Xin Chen, Sergey Kovalev, Jacek Blazewicz |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Maximization 01 natural sciences Upper and lower bounds Scheduling (computing) Due date 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Minification Optimal criterion Mathematics |
| Zdroj: | Discrete Applied Mathematics. 290:71-78 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.05.023 |
| Popis: | In this paper, we consider four semi-online scheduling problems with the goal of early work maximization, which shares the same essence with late work minimization when the optimal offline solutions are determined, but differs from it when the approximation or online solutions are constructed. First, we prove a tight bound 6 5 for scheduling jobs with a common due date when assuming that the total processing time of all jobs, or, the optimal criterion value is known in advance. Then, we show that if both the total and maximal processing time is known, the bound can be reduced to 10 9 and it is still tight. Finally, we prove that if only know the maximal processing time, the upper and lower bounds are 1.1375 and 1.1231, respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect