Formulating the single machine sequencing problem with release dates as a mixed integer program
type: Item
instance of: scholarly article
title: Formulating the single machine sequencing problem with release dates as a mixed integer program
zbMATH Open document ID: 0694.90060
DOI: 10.1016/0166-218X(90)90104-K
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C11
zbMATH DE Number: 4137520
zbMATH Keywords: sequencing
zbMATH Keywords: single machine
zbMATH Keywords: release dates
zbMATH Keywords: weighted sum of start times
zbMATH Keywords: weighted sum of completion times
zbMATH Keywords: sequence of relaxations
zbMATH Keywords: lower bounds
Wikidata QID: Q56324122
author: Martin Dyer
author: Laurence A. Wolsey
reviewed by: Ya. M. Shafransky
MaRDI profile type: Publication
cites work: On the facial structure of scheduling polyhedra
cites work: An algorithm for single machine sequencing with release dates to minimize total weighted completion time
cites work: Q4194705
cites work: Q3790929
cites work: Minimizing Weighted Completion Times with Deadlines
cites work: A Sequencing Problem with Release Dates and Clustered Jobs
cites work: An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
cites work: Q4068433
full work available at URL: 0166-218x(90)90104-k
OpenAlex ID: W2159152246
DBLP publication ID: journals/dam/DyerW90
description: scientific article; zbMATH DE number 4137520