Improved algorithm for a generalized on-line scheduling problem on identical machines

Improved algorithm for a generalized on-line scheduling problem on identical machines

0.00 Avg rating0 Votes
Article ID: iaor20084373
Country: Netherlands
Volume: 176
Issue: 1
Start Page Number: 643
End Page Number: 652
Publication Date: Jan 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.