Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1148144 | Journal of Statistical Planning and Inference | 2010 | 4 Pages |
Abstract
Machine scheduling and covering problems may occur in many applications such as load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc. In this paper we study machine covering problems with combined partial information on m parallel identical machines. We consider sequences where the processing time of all jobs are at most 1/k1/k times of the optimal value (for an integer k). For the case where the optimal value is not known in advance, we show that LS algorithm is optimal. For the case where the optimal value is known in advance, we give lower bounds and present semi-online algorithms.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yong Wu, Qifan Yang, Yikun Huang,