One-pass batching algorithms for the one-machine problem (Q1113792)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4081278
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | One-pass batching algorithms for the one-machine problem |
scientific article; zbMATH DE number 4081278 |
Statements
One-pass batching algorithms for the one-machine problem (English)
0 references
1988
0 references
This paper deals with the problem of batching jobs which must be processed on a single machine. In the case the jobs are all of one type and the objective is to minimize the sum of completion times, it is shown that the greedy algorithm solves this problem. In the case of various job types, a heuristic is given. The heuristic has provided very good results on randomly generated examples.
0 references
single machine
0 references
sum of completion times
0 references
greedy algorithm
0 references
various job types
0 references
heuristic
0 references
0.8686272501945496
0 references
0.8305001258850098
0 references
0.8215090036392212
0 references
