Single Machine Scheduling with Release Dates.

We consider the scheduling problem of minimizing the average wighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n logn) greedy algorithm leads to optimal solutions to both relaxations.

MoreLess

Year of publication:	1999
Authors:	Goemans, M.X. ; Queyranne, M. ; Schulz, A.S. ; Skutella, M. ; Wang, Y.
Institutions:	Center for Operations Research and Econometrics (CORE), École des Sciences Économiques de Louvain
Subject:	LINEAR PROGRAMMING

More details

Series:	Papers.
Type of publication:	Book / Working Paper
Notes:	33 pages
Classification:	C61 - Optimization Techniques; Programming Models; Dynamic Analysis ; C60 - Mathematical Methods and Programming. General
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005634099