A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

作者：Yuan Jinjiang^*; Li Shisheng; Tian Ji; Fu Ruyan

来源：Journal of Combinatorial Optimization, 2009, 17(2): 206-213.

DOI：10.1007/s10878-007-9108-y

• Scheduling
• On-line algorithm
• Parallel-batching
• Delivery time

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J(j), its processing time and delivery time are denoted by p(j) and q(j), respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J(j), q(j) <= p(j); (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J(i) and J(j), p(i) > p(j) implies q(i) >= q(j). We provide an on-line algorithm with competitive ratio (root 5 + 1)/2 for both problems, and the results are the best possible.

• 出版日期2009-2
• 单位郑州大学