Formulating the single machine sequencing problem with release dates as a mixed integer program (Q909575)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Formulating the single machine sequencing problem with release dates as a mixed integer program |
scientific article |
Statements
Formulating the single machine sequencing problem with release dates as a mixed integer program (English)
0 references
1990
0 references
The paper deals with the problem of sequencing n jobs for single machine processing when release dates of jobs are given. The subject is to minimize the weighted sum of start times of jobs (or, equivalently, weighted sum of completion times). The authors consider a sequence of relaxations of the problem. The relaxations consist in replacing release dates for equal jobs by zeros. The relaxed problems are formulated in terms of linear programming problems. One of the main results described in the papeer lies in obtaining new lower bounds for the initial problem.
0 references
sequencing
0 references
single machine
0 references
release dates
0 references
weighted sum of start times
0 references
weighted sum of completion times
0 references
sequence of relaxations
0 references
lower bounds
0 references
0 references
0 references
