Approximability of scheduling with fixed jobs

DOI<267::AID-JOS31>3.0.CO;2-H 10.1002/(SICI)1099-1425(199911/12)2:6<267::AID-JOS31>3.0.CO;2-HzbMath0953.90025MaRDI QIDQ1964484

Angelika Steger, Horst Weisser, Mark Scharbrodt

Publication date: 1 February 2001

Published in: Journal of Scheduling (Search for Journal in Brave)

zbMATH Keywords

schedulingmakespanpolynomial approximation scheme

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (17)

Approximability of single machine scheduling with fixed jobs to minimize total completion time ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption ⋮ Minimizing total weighted completion time with an unexpected machine unavailable interval ⋮ Single machine unbounded parallel-batch scheduling with forbidden intervals ⋮ Scheduling on same-speed processors with at most one downtime on each machine ⋮ Approximation for scheduling on uniform nonsimultaneous parallel machines ⋮ Approximation schemes for parallel machine scheduling with availability constraints ⋮ SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES ⋮ Multi-agent scheduling on a single machine with max-form criteria ⋮ Scheduling on uniform processors with at most one downtime on each machine ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria ⋮ Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs ⋮ Approximation algorithms for scheduling with reservations ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS

Cites Work

• Unnamed Item
• Bin packing can be solved within 1+epsilon in linear time
• Integer Programming with a Fixed Number of Variables
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Approximability of scheduling with fixed jobs