| Article ID: | iaor20081704 |
| Country: | Singapore |
| Volume: | 24 |
| Issue: | 3 |
| Start Page Number: | 373 |
| End Page Number: | 382 |
| Publication Date: | Jun 2007 |
| Journal: | Asia-Pacific Journal of Operational Research |
| Authors: | Cai Sheng-Yi |
| Keywords: | production, programming: mathematical |
This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system of m (m ⩾ 3) identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times are known in advance. In the second case, we assume that the total processing times of all jobs are known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is 1/m−1, which is shown to be the best possible competitive ratio for each semi-online problem.