Formulating the single machine sequencing problem with release dates as a mixed integer program (Q909575)

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.