Machine covering with combined partial information

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 / 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.