Monaldo Mastrolilli
Abstract
We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known inapproximability result says that it is NP-hard to approximate job shops within a factor less than 5/4. Closing this big approximability gap is a well-known and long-standing open problem.
This article closes many gaps in our understanding of the hardness of this problem and answers several open questions in the literature. It is shown the first nonconstant inapproximability result that almost matches the best-known approximation algorithm for acyclic job shops. The same bounds hold for the general version of flow shops, where jobs are not required to be processed on each machine. Similar inapproximability results are obtained when the objective is to minimize the sum of completion times. It is also shown that the problem with two machines and the preemptive variant with three machines have no PTAS.
- Alimonti, P. and Kann, V. 2000. Some APX-completeness results for cubic graphs. Theoret. Comput. Science 237, 1-2, 123--134. Google Scholar
Digital Library
- Anderson, E. J., Jayram, T. S., and Kimbrel, T. 2001. Tighter bounds on preemptive job shop scheduling with two machines. Computing 67, 1, 83--90. Google ScholarDigital Library
- Bansal, N., Kimbrel, T., and Sviridenko, M. 2006. Job shop scheduling with unit processing times. Math. Oper. Res. 31, 381--389. Google ScholarDigital Library
- Beck, J. 1991. An algorithmic approach to the lovasz local lemma. Random Struct. Algor. 2, 4, 343--365. Google ScholarDigital Library
- Chen, B., Potts, C. N., and Woeginger, G. J. 1998. A review of machine scheduling: Complexity, algorithms and approximability. Hand. Combin. Optimiz. 3, 21--169.Google Scholar
- Czumaj, A. and Scheideler, C. 2000. A new algorithm approach to the general lovász local lemma with applications to scheduling and satisfiability problems (extended abstract). In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). 38--47. Google ScholarDigital Library
- Feige, U. and Scheideler, C. 2002. Improved bounds for acyclic job shop scheduling. Combinatorica 22, 3, 361--399.Google ScholarCross Ref
- Fishkin, A., Jansen, K., and Mastrolilli, M. 2003. On minimizing average weighted completion time: A PTAS for the job shop problem with release dates. In Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC’03). Lecture Notes in Computer Science, vol. 2906, Springer, 319--328.Google ScholarCross Ref
- Fishkin, A. V., Jansen, K., and Mastrolilli, M. 2008. Grouping techniques for scheduling problems: Simpler and faster. Algorithmica 51, 2, 183--199. Google ScholarDigital Library
- Goldberg, L. A., Paterson, M., Srinivasan, A., and Sweedyk, E. 2001. Better approximation guarantees for job-shop scheduling. SIAM J. Disc. Math. 14, 1, 67--92. Google ScholarDigital Library
- Graham, R., Lawler, E., Lenstra, J., and Kan, A. R. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5, 287--326.Google ScholarCross Ref
- Hoogeveen, H., Schuurman, P., and Woeginger, G. J. 2001. Non-approximability results for scheduling problems with minsum criteria. INFORMS J. Comput. 13, 2, 157--168. Google ScholarDigital Library
- Jansen, K., Solis-Oba, R., and Sviridenko, M. 2003. Makespan minimization in job shops: A linear time approximation scheme. SIAM J. Disc. Math. 16, 2, 288--300. Google ScholarDigital Library
- Khot, S. 2001. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS). 600--609. Google ScholarDigital Library
- Lawler, E. L., Lenstra, J., Kan, A. R., and Shmoys, D. 1993. Sequencing and scheduling: Algorithms and complexity. Handb. Oper. Res. Manage. Sci. 4, 445--522.Google ScholarCross Ref
- Leighton, F. T., Maggs, B. M., and Rao, S. B. 1994. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14, 2, 167--180.Google ScholarCross Ref
- Leighton, F. T., Maggs, B. M., and Richa, A. W. 1999. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375--401.Google ScholarCross Ref
- Nagarajan, V. and Sviridenko, M. 2008. Tight bounds for permutation flow shop scheduling. In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO). 154--168. Google ScholarDigital Library
- Potts, C., Shmoys, D., and Williamson, D. 1991. Permutation vs. nonpermutation flow shop schedules. Oper. Res. Lett. 10, 281--284.Google ScholarDigital Library
- Queyranne, M. and Sviridenko, M. 2002. Approximation algorithms for shop scheduling problems with minsum objective. J. Sched. 5, 4, 287--305.Google ScholarCross Ref
- Schuurman, P. and Woeginger, G. J. 1999. Polynomial time approximation algorithms for machine scheduling: ten open problems. J. Sched. 2, 5, 203--213.Google ScholarCross Ref
- Sevastianov, S. V. and Woeginger, G. J. 1998. Makespan minimization in preemptive two machine job shops. Computing 60, 1, 73--80. Google ScholarDigital Library
- Shmoys, D., Stein, C., and Wein, J. 1994. Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23, 617--632. Google ScholarDigital Library
- Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevastianov, S. V., and Shmoys, D. B. 1997. Short shop schedules. Oper. Res. 45, 288--294.Google ScholarDigital Library
Index Terms
- Hardness of Approximating Flow and Job Shop Scheduling Problems
Recommendations
A neighborhood for complex job shop scheduling problems with regular objectives
Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer ...
Heuristic Optimization for Dual-resource Constrained Job Shop Scheduling
CAR '09: Proceedings of the 2009 International Asia Conference on Informatics in Control, Automation and RoboticsIn the study of job shop scheduling problem in mass injection molding processing enterprises, the practical job shop scheduling environment cannot be mirrored in the traditional study only considering machine resources. A dual-resource (machines and ...
New hardness results for congestion minimization and machine scheduling
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computingWe study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. We are given a directed capacitated graph and a set of source-sink pairs. The goal is to route all pairs with minimum ...
Comments