An improved on-line algorithm for single parallel-batch machine scheduling with delivery times (Q423933): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: H. S. Yoon / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68M20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6039487 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
on-line scheduling | |||
Property / zbMATH Keywords: on-line scheduling / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
parallel-batch machine | |||
Property / zbMATH Keywords: parallel-batch machine / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
delivery times | |||
Property / zbMATH Keywords: delivery times / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
competitive ratio | |||
Property / zbMATH Keywords: competitive ratio / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2011.12.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2080477217 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation algorithms in batch processing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal on-line algorithms for one batch machine with grouped processing times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3995531 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing makespan on a single batch processing machine with dynamic job arrivals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient Algorithms for Scheduling Semiconductor Burn-In Operations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A flexible on-line scheduling algorithm for batch machine with infinite capacity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On-line scheduling algorithms for a batch machine with finite capacity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On-line scheduling with delivery time on a single batch machine / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On-line algorithms for minimizing makespan on batch processing machines / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:29, 5 July 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
0 references
0 references
0 references