|
|||||
|
|
On-line scheduling of small open shops |
|
| Authors: | Bo Chen Donglei Du Jiye Han Jianjun Wen |
| Affiliation: | a Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK b School of Management, University of Texas at Dallas, Richardson, TX 75083, USA c Institute of Applied Mathematics, Chinese Academy of Sciences, P.O. Box 2734, Beijing, 100080, People's Republic of China d Department of Computer Science, University of California, Riverside, CA 92521, USA |
| Abstract: | We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive. |
| Keywords: | Scheduling On-line Open shop Preemption Competitive analysis |
| 本文献已被 ScienceDirect 等数据库收录！ | |