Two Special Models Of On-line Batch Scheduling

In this paper, we mainly consider two special models on-line batch scheduling problem.On-line, in this paper, means on-line-time. All job's information is unknown before their release times , and once a job is scheduled it cannot be changed. The parallel batching scheduling means that a machine can process several jobs simultaneously as a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is equal to the longest processing time of the jobs assigned to it.First of all, we investigate the single machine parallel batching scheduling problem . The main results of this paper are as follows.(1)Problem 1|p - batch,b = 3;p_j = 1; on - line;r_i;limited restarts|C_max . We show that there is no on-line algorithm with competitive ratio less than (?), and present a best possible on-line algorithm.(2)Problem 1|p - batch, b = 3; on - line, r_i; limited restarts|C_max. We show that there is no on-line algorithm with competitive ratio less than (?), and present an on-line algorithm with competitive ratio (?).Then, we discuss an on-line parallel batching scheduling problem with special jobs. Here, all jobs are on-line. There are some jobs , of which each has to schedule in a single batch respectively and must be precessed once it comes. We call them special jobs, and others common jobs. The main results of this paper are as follows.(1)Problem 1|special job(restart);p_j = 1; on - line, r_i, D|Σf_j. We show that there is no on-line algorithm with competitive ratio more than (?), and present a best possible on-line algorithm.(2)Problem P₂|special job(pmtn);p - batch, b =∞; on - line, r_i|C_max. We show that there is a no on-line algorithm with competitive ratio less than (?) and present a on-line algorithm with competitive ratio (?).(3)Problem P₂|special job(restart);p - batch, b =∞; on -line, r_i|C_max . We show that there is no on-line algorithm with competitive ratio less than 2, and present a best possible on-line algorithm.