Approximability of scheduling with fixed jobs
Scheduling problems of minimizing the makespan on identical parallel machines are among the most well-studied problems -- especially in the field of approximation. In modern industrial software however, it has become standard to work on a variant of this problem, where some of the jobs are already fixed in the schedule. The remaining jobs are to be assigned to the machines in such a way that they do not overlap with fixed jobs. This problem variant is the root of many real-world scheduling problems where pre-assignments on the machines are considered, such as cleaning times or jobs that have already started. In this paper the authors investigate the approximability of the scheduling problem with fixed jobs. They present a Polynomial-Time Approximation Scheme (PTAS) for the case that the number \(m\) of machines is constant. For this PTAS they propose a new technique by partitioning an underlying packing problem into a reasonable unrelated family of restricted bin packing problems. They also generalize the PTAS to the case that the machines are independent and run at different speeds. Moreover, they demonstrate that, assuming P\(\neq\)NP, there is no arbitrarily close approximation in the general case when the number of machines is part of the input. This is extended by showing that there is no asymptotic PTAS in the general machine case. We finally show that there exists no FPTAS in the constant machine case, unless P\(=\)NP. These results contrast to the classical problem of minimizing the makespan where the existence of a PTAS resp. of an FPTAS for the variable resp. the constant machine case has been proven.
- Improved approximation algorithms for scheduling with fixed jobs
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
- Approximation algorithms for scheduling with reservations
- On the optimality of approximation schemes for the classical scheduling problem
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- An Application of Bin-Packing to Multiprocessor Scheduling
- Bin packing can be solved within 1+epsilon in linear time
- Bounds for Certain Multiprocessing Anomalies
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- FPT approximation algorithm for scheduling with memory constraints
- Approximation for scheduling on uniform nonsimultaneous parallel machines
- Scheduling on uniform processors with at most one downtime on each machine
- Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria
- Job release scheduling problem: complexity and an approximation algorithm
- Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation
- Minimizing total weighted late work on a single-machine with non-availability intervals
- Fixed-order scheduling on parallel machines
- Single machine unbounded parallel-batch scheduling with forbidden intervals
- Multi-agent scheduling on a single machine with max-form criteria
- Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs
- Tight approximation algorithms for scheduling with fixed jobs and nonavailability
- MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS
- SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- The Fixed Job Schedule Problem with Working-Time Constraints
- Minimizing total weighted completion time with an unexpected machine unavailable interval
- Scheduling on same-speed processors with at most one downtime on each machine
- Improved approximation algorithms for scheduling with fixed jobs
- scientific article; zbMATH DE number 1839470 (Why is no real title available?)
- Formulating a scheduling problem with almost identical jobs by using positional completion times
- Scheduling partially ordered jobs faster than \(2^n\)
- On the optimality of approximation schemes for the classical scheduling problem
- Approximation algorithms for scheduling with reservations
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
- Approximation schemes for parallel machine scheduling with availability constraints
- Fixed-time schedules for the processing of jobs when service completions are not observable
- Approximability of single machine scheduling with fixed jobs to minimize total completion time
- Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption
- Scheduling and fixed-parameter tractability
- A scheduling problem with job values given as a power function of their completion times
This page was built for publication: Approximability of scheduling with fixed jobs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1964484)
