Semi-online scheduling problems on a small number of machines |
| |
Authors: | Kangbok Lee Kyungkuk Lim |
| |
Affiliation: | 1. Department of Supply Chain Management & Marketing Sciences, Rutgers Business School, 1 Washington Park, Newark, NJ, 07102, USA 2. BK21 Project, Sogang Business School, Shinsu-dong 1, Mapo-gu, Seoul, 121-742, Republic of Korea
|
| |
Abstract: | We consider the semi-online parallel machine scheduling problem of minimizing the makespan given a priori information: the total processing time, the largest processing time, the combination of the previous two or the optimal makespan. We propose a new algorithm that can be applied to the problem with the known total or largest processing time and prove that it has improved competitive ratios for the cases with a small number of machines. Improved lower bounds of the competitive ratio are also provided by presenting adversary lower bound examples. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|