- Title
- A bucket indexed formulation for nonpreemptive single machine scheduling problems
- Creator
- Boland, Natashia; Clement, Riley; Waterer, Hamish
- Relation
- Funding BodyARCGrant NumberLP0990739 http://purl.org/au-research/grants/arc/LP0990739
- Relation
- INFORMS Journal on Computing Vol. 28, Issue 1, p. 14-30
- Publisher Link
- http://dx.doi.org/10.1287/ijoc.2015.0661
- Publisher
- Institute for Operations Research and the Management Sciences (INFORMS)
- Resource Type
- journal article
- Date
- 2016
- Description
- A new mixed-integer linear programming (MILP) formulation for nonpreemptive single machine scheduling problems is presented. The model is a generalisation of the classical time indexed (TI) model to one in which at most two jobs can be processing in each time period. Like the TI model, the new model, called the bucket indexed (BI) model, partitions the planning horizon into periods of equal length, or buckets. Unlike the TI model, the length of a period is a parameter of the BI model and can be chosen to be as long as the processing time of the shortest job. The two models are equivalent if a period is of unit length, but when longer periods are used in the BI model, it can have significantly fewer variables and nonzeros than the corresponding TI model. A computational study using weighted tardiness instances, and weighted completion time instances with release dates, reveals that the BI model significantly outperforms the TI model on instances where the minimum processing time of the jobs is large. Furthermore, the performance of the BI model is less vulnerable to increases in average processing time when the ratio of the largest processing time to the smallest is held constant.
- Subject
- single machine scheduling; mixed-integer linear programming; time indexed formulations
- Identifier
- http://hdl.handle.net/1959.13/1323032
- Identifier
- uon:24718
- Identifier
- ISSN:1091-9856
- Language
- eng
- Reviewed
- Hits: 1366
- Visitors: 1358
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|