A common approximation framework for early work, late work, and resource leveling problems
From MaRDI portal
(Redirected from Publication:2184097)
Abstract: We study the approximability of two related machine scheduling problems. In the late work minimization problem, there are identical parallel machines and the jobs have a common due date. The objective is to minimize the late work, defined as the sum of the portion of the jobs done after the due date. A related problem is the maximization of the early work, defined as the sum of the portion of the jobs done before the due date. We describe a polynomial time approximation scheme for the early work maximization problem, and we extended it to the late work minimization problem after shifting the objective function by a positive value that depends on the problem data. We also prove an inapproximability result for the latter problem if the objective function is shifted by a constant which does not depend on the input. These results remain valid even if the number of the jobs assigned to the same machine is bounded. This leads to an extension of our approximation scheme to some variants of the resource leveling problem, for which no approximation algorithms were known.
Recommendations
- Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
- A parallel machine scheduling problem maximizing total weighted early work
- Approximation algorithms for scheduling a single machine to minimize total late work
- Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
- A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
Cites work
- A branch-and-cut algorithm for scheduling of projects with variable-intensity activities
- A comment on scheduling two parallel machines with capacity constraints
- A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work
- A metaheuristic solution approach for the time-constrained project scheduling problem
- A note on the two machine job shop with the weighted late work criterion
- Approximation algorithms for scheduling a single machine to minimize total late work
- Approximation schemes for scheduling jobs with common due date on parallel machines to minimize Total tardiness
- Bounds on Multiprocessing Timing Anomalies
- Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
- scientific article; zbMATH DE number 3902030 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Mixed-integer linear programming for resource leveling problems
- Open shop scheduling problems with late work criteria.
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
- Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints
- Resource leveling in a machine environment
- Scheduling on parallel identical machines with late work criterion: offline and online cases
- Single Machine Scheduling to Minimize Total Late Work
- The two-machine flow-shop problem with weighted late work criterion and common due date
Cited in
(14)- Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work
- Combinatorial approximation algorithms for the maximum bounded connected bipartition problem
- Two-machine flow shop scheduling with a common due date to maximize total early work
- Approximation algorithms for the maximum bounded connected bipartition problem
- Scheduling with competing agents, total late work and job rejection
- A parallel machine scheduling problem maximizing total weighted early work
- Improved approximation schemes for early work scheduling on identical parallel machines with a common due date
- Online early work scheduling on parallel machines
- Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems
- Approximation results on resource leveling problems
- Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work
- Approximation schemes for parallel machine scheduling to maximize total weighted early work with a common due date
- Scheduling with a discounted profit criterion on identical machines
- Minimizing the maximum late work for a single-machine scheduling problem with flexible maintenance activities
This page was built for publication: A common approximation framework for early work, late work, and resource leveling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184097)
