Minimizing machine assignment costs over Δ-approximate solutions of the scheduling problem P||Cmax
Explore this paper's citation graph
Summary
A problem of minimizing the total machine assignment cost over the Δ-approximate solutions of the makespan minimization problem is introduced and it is proved that this new problem is strongly NP-hard and pseudo-polynomially non- approximable in general.
- Type
- article
- Published
- 2019-11-12
- Cited by
- 4
- References
- 13
- OpenAlex
- https://openalex.org/W2950713857
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:197481837
Keywords
Job shop scheduling, Lexicographical order, Approximation algorithm, Mathematical optimization, Minification
References
- Fast approximation algorithms for bi-criteria scheduling with machine assignment costs
- A note on an open‐end bin packing problem
- Multi-product lot sizing and scheduling on unrelated parallel machines
- An approximation algorithm for the generalized assignment problem
- On the exact upper bound for the multifit processor scheduling algorithm
- Bi-criteria scheduling with machine assignment costs
- Using dual approximation algorithms for scheduling problems: Theoretical and practical results
- Bounds on Multiprocessing Timing Anomalies
- Fundamentals of Parameterized Complexity
- The NP-Completeness Column: An Ongoing Guide
- An efficient approximation for the Generalized Assignment Problem
- Polynomiality for Bin Packing with a Constant Number of Item Types
- Parameterized Algorithms
Cited by
- Unrelated parallel machine scheduling with processing cost, machine eligibility and order splitting
- Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing
- The generalized assignment problem with fixed processing times and uniform processing costs to minimize total cost
Related papers
- Fully polynomial time approximation scheme for makespan minimization problem on two-machine with a fixed non-availability interval
- Improved approximation algorithms for two-stage flowshops scheduling problem
- A constant-factor approximation algorithm for multi-vehicle collection for processing problem
- Approximation Schemes for 0-1 Knapsack
- Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval
- Approximation schemes for minimizing average weighted completion time with release dates