An improved on-line algorithm for single parallel-batch machine scheduling with delivery times (Q423933)

Scheduling algorithms are approximation algorithms which assign jobs to the execution units of a machine such that a low overall processing time results. Due to the different nature of jobs, machines or information available, there exists a large variety of specific scheduling problems and each problem requires its own scheduling algorithms. In this article, a specific scheduling algorithm is proposed together with theorems and proofs concerning its quality. The contents is very well described by its abstract: ``We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio \(\approx 1.828\) source, which improves on a 2-competitive on-line algorithm for this problem in the literature.'' The article is written in a mathematical and formal style.