An improved on-line algorithm for single parallel-batch machine scheduling with delivery times (Q423933): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved on-line algorithm for single parallel-batch machine scheduling with delivery times |
scientific article |
Statements
An improved on-line algorithm for single parallel-batch machine scheduling with delivery times (English)
0 references
30 May 2012
0 references
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.
0 references
on-line scheduling
0 references
parallel-batch machine
0 references
delivery times
0 references
competitive ratio
0 references