On-line problems of minimizing makespan on a single batch processing machine with nonidentical job sizes (Q2574421)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On-line problems of minimizing makespan on a single batch processing machine with nonidentical job sizes |
scientific article |
Statements
On-line problems of minimizing makespan on a single batch processing machine with nonidentical job sizes (English)
0 references
21 November 2005
0 references
A set of jobs has to be scheduled on a batching machine. All jobs arrive at their release dates and any job is characterized by its size and its processing time. However information about each job is made available at its arrival time. All jobs scheduled in the same batch start and finish simultaneously. The processing time of a batch is the largest processing time of its jobs. The total size of jobs prescribed to the same batch is not greater than the capacity of the machine. The purpose is to schedule all jobs in batches so as to minimize the makespan. For this problem a simple 7/2-competitive algorithm is proposed. When there are only two distinct arrival times a 119/44-competitive algorithm is developed. If the problem satisfies proportional assumptions the algorithms are improved to 3-competitive and 12/5-competitive, respectively.
0 references
on-line
0 references
scheduling
0 references
makespan
0 references
competitive algorithm
0 references
