A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
type: Item
instance of: scholarly article
title: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
zbMATH Open document ID: 0958.90042
DOI: 10.1016/S0167-6377(99)00056-5
author: F. Chudak
author: Dorit S. Hochbaum
published in: Operations Research Letters
publication date: 2001-04-19T00:00:00Z
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 1419831
zbMATH Keywords: nonpreemptive scheduling problem
zbMATH Keywords: precedence constraints
zbMATH Keywords: linear programming relaxation
MaRDI profile type: Publication
cites work: The permutahedron of series-parallel posets
cites work: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
cites work: Matrix multiplication via arithmetic progressions
cites work: A new approach to the maximum-flow problem
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
cites work: An algorithm for the single machine sequencing problem with precedence constraints
cites work: Structure of a simple scheduling polyhedron
cites work: Q3204309
full work available at URL: s0167-6377(99)00056-5
OpenAlex ID: W1992370758
Wikidata QID: Q127125105
description: scientific article; zbMATH DE number 1419831