Scheduling precedence-constrained jobs with stochastic processing times on parallel machines
| dc.contributor.author | Skutella, Martin | |
| dc.contributor.author | Uetz, Marc | |
| dc.date.accessioned | 2022-05-11T12:11:43Z | |
| dc.date.available | 2022-05-11T12:11:43Z | |
| dc.date.issued | 2000 | |
| dc.description.abstract | We consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the weighted sum of job completion times &;j wjC_j in expectation, where wj&; 0. Building upon an LP-relaxation by Möhring, Schulz, and Uetz (J.ACM 46 (1999), pp.924-942) and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein (SIAM J. Comp., to appear) we derive the first approximation algorithms for this model. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/16900 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-15678 | |
| dc.language.iso | en | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | scheduling problems | en |
| dc.subject.other | approximation algorithm | en |
| dc.title | Scheduling precedence-constrained jobs with stochastic processing times on parallel machines | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2000, 691 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90B35 Deterministic scheduling theory in operations research | en |
| tub.subject.msc2000 | 90C59 Approximation methods and heuristics in mathematical programming | en |