Improved algorithm for a generalized on-line scheduling problem on identical machines |
| |
| Authors: | Rongheng Li Huei-Chuen Huang |
| |
| Institution: | 1. Department of Mathematics, Hunan Normal University, Changsha 410081, China;2. Department of Industrial and Systems Engineering, National University of Singapore, 1 Engineering Drive 2, Singapore 117576, Singapore |
| |
| Abstract: | This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. In this problem, jobs arrive in form of order before its release time and decisions have to be made whenever an order is placed and the orders arrive according to any sequence. A heuristic algorithm, NMLS, better than MLS is given for any m ? 2. The competitive ratio is improved from 2.93920 to 2.78436. |
| |
| Keywords: | Scheduling Heuristic On-line List scheduling Competitive ratio |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
