article

Free access

Computer-Aided complexity classification of combinational problems

Authors:

A. H. G. Rinnooy KanAuthors Info & Claims

Communications of the ACM, Volume 25, Issue 11

Pages 817 - 822

https://doi.org/10.1145/358690.363066

Published: 01 November 1982 Publication History

Abstract

We describe a computer program that has been used to maintain a record of the known complexity results for a class of 4536 machine scheduling problems. The input of the program consists of a listing of known “easy” problems and a listing of known “hard” problems. The program employs the structure of the problem class to determine the implications of these results. The output provides a listing of essential results in the form of maximal easy and minimal hard problems as well as listings of minimal and maximal open problems, which are helpful in indicating the direction of future research. The application of the program to a restricted class of 120 single-machine problems is demonstrated. Possible refinements and extensions to other research areas are suggested. It is also shown that the problem of determining the minimum number of results needed to resolve the status of all remaining open problems in a complexity classification such as ours is itself a hard problem.

References

[1]

Baker, K.R. Introduction to Sequencing and Scheduling. Wiley, New York, 1974.

[2]

Blazewicz, J. Scheduling dependent tasks with different arrival times to meet deadlines. In E. Gelenbe (Ed.), Modelling and Performance Evaluation of Computer Systems, Elsevier Science, New York, Amsterdam, 1976, pp. 57-65.

Digital Library

[3]

Coffman, E.G. Jr. and Graham, R.L. Optimal scheduling for two-processor systems.,4cta Inf. 1 (1972), 200-213.

[4]

Garey, M.R. and Johnson, D.S. "Strong" NP-completeness results: Motivation, examples and implications. JACM 25 (1978), 499-508.

Digital Library

[5]

Garey, M.R. and Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

Digital Library

[6]

Graham, R.L., Lawler, E.L, Lenstra, J.K. and Rinnooy Kan, A.H.G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5, (1979), 287-326.

[7]

Horn, W. A. Single-machine job sequencing with treelike precedence ordering and linear delay penalties. SIAM J. Appl. Math. 23 (1972), 189-202.

Digital Library

[8]

Karp, R.M. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85-103.

[9]

Labetoulle, J., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. Preemptive scheduling of uniform machines subject to release dates. Report BW 99, Mathematisch Centrum, Amsterdam, The Netherlands, 1979.

[10]

Lageweg, B.J., Lawler, E.L., and Lenstra, J.K. Machine scheduling problems: Computations, complexity and classification. In honour of A.H.G. Rinnooy Kan upon the occasion of the defense of his doctoral thesis, January 28, 1976. Report BN 30, Mathematisch Centrum, Amsterdam, The Netherlands, 1976 (out of print).

[11]

Lageweg, B.J., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G. Computer aided complexity classification of deterministic scheduling problems. Report BW 138, Mathematisch Centrum, Amsterdam, The Netherlands, 1981.

[12]

Lawler, E.L. A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1 (1977), 331-342.

[13]

Lawler, E.L. Optimal sequencing of a single machine subject to precedence constraints. Management Sci. 19 (1973), 544-546.

Digital Library

[14]

Lawler, E.L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math. 2 (1978), 75-90.

[15]

Lawler, E.L. Unpublished result, 1981.

[16]

Lenstra, J.K. Unpublished results, 1980 and 1982.

[17]

Lenstra, J.K. and Rinnooy Kan, A.H.G. Complexity of scheduling under precedence constraints. Oper. Res. 26 (1978), 22-35.

Digital Library

[18]

Lenstra, J.K. and Rinnooy Kan, A.H.G. Complexity results for scheduling chains on a single machine. European J. Oper. Res. 4 (1980), 270-275.

[19]

Lenstra, J.K. and Rinnooy Kan, A.H.Gi Computational complexity of discrete optimization problems. Ann. Discrete Math. 4 (1979), 121-140.

[20]

Lenstra, J.K., Rinnooy Kan, A.H.G., and Brucker, P. Complexity of machine scheduling problems. Ann. Discrete Math. 1 (1977), 343-362.

[21]

Sidney, J.B. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23 (1975), 283-298.

Digital Library

Cited By

Zhao MMo LLiu JHan JNiu D(2024)GAT-based Deep Reinforcement Learning Algorithm for Real-time Task Scheduling on Multicore Platform2024 36th Chinese Control and Decision Conference (CCDC)10.1109/CCDC62350.2024.10587381(5674-5679)Online publication date: 25-May-2024
https://doi.org/10.1109/CCDC62350.2024.10587381
Zhadan AAllahverdyan AKondratov IMikheev VPetrosian ORomanovskii AKharin V(2023)Multi-agent Reinforcement Learning-based Adaptive Heterogeneous DAG SchedulingACM Transactions on Intelligent Systems and Technology10.1145/361030014:5(1-26)Online publication date: 3-Oct-2023
https://dl.acm.org/doi/10.1145/3610300
Liu YXu BHuangfu WYin H(2023)Nickel-based polycrystalline superalloy composition design framework based on non-dominated sorting genetic algorithm IIComputational Materials Science10.1016/j.commatsci.2023.112065220(112065)Online publication date: Mar-2023
https://doi.org/10.1016/j.commatsci.2023.112065
Show More Cited By

Index Terms

Computer-Aided complexity classification of combinational problems
1. Theory of computation

Recommendations

The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization
Special issue: Efficient algorithms

The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown NP-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation ...
Free Bits, PCPs, and Nonapproximability---Towards Tight Results

This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP -optimization problems. The emphasis is on proving tight nonapproximability results via consideration of measures ...
Complexity Analysis of Generalized and Fractional Hypertree Decompositions

Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive ...

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 25, Issue 11

Nov 1982

82 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/358690

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago,IL

Issue’s Table of Contents

Copyright © 1982 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1982

Published in CACM Volume 25, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
927
Total Downloads

Downloads (Last 12 months)116
Downloads (Last 6 weeks)17

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao MMo LLiu JHan JNiu D(2024)GAT-based Deep Reinforcement Learning Algorithm for Real-time Task Scheduling on Multicore Platform2024 36th Chinese Control and Decision Conference (CCDC)10.1109/CCDC62350.2024.10587381(5674-5679)Online publication date: 25-May-2024
https://doi.org/10.1109/CCDC62350.2024.10587381
Zhadan AAllahverdyan AKondratov IMikheev VPetrosian ORomanovskii AKharin V(2023)Multi-agent Reinforcement Learning-based Adaptive Heterogeneous DAG SchedulingACM Transactions on Intelligent Systems and Technology10.1145/361030014:5(1-26)Online publication date: 3-Oct-2023
https://dl.acm.org/doi/10.1145/3610300
Liu YXu BHuangfu WYin H(2023)Nickel-based polycrystalline superalloy composition design framework based on non-dominated sorting genetic algorithm IIComputational Materials Science10.1016/j.commatsci.2023.112065220(112065)Online publication date: Mar-2023
https://doi.org/10.1016/j.commatsci.2023.112065
Potts CStrusevich V(2017)Fifty years of scheduling: a survey of milestonesJournal of the Operational Research Society10.1057/jors.2009.260:sup1(S41-S68)Online publication date: 21-Dec-2017
https://doi.org/10.1057/jors.2009.2
Batsyn MGoldengorin BPardalos PSukhov P(2014)Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion timeOptimization Methods & Software10.1080/10556788.2013.85436029:5(955-963)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1080/10556788.2013.854360
Zack Y(2012)Developing feasible and optimal schedules of jobs on one machineCybernetics and Systems Analysis10.1007/s10559-012-9392-048:1(51-66)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1007/s10559-012-9392-0
Sizyukhin K(2009)Models and methods for increasing of service provider competitive advantage by minimizing quoted in customers' SLA service fulfillment flow timesIEEE EUROCON 200910.1109/EURCON.2009.5167902(1879-1882)Online publication date: May-2009
https://doi.org/10.1109/EURCON.2009.5167902
Dessouky MLageweg BLenstra Jvan de Velde S(2008)Scheduling identical jobs on uniform parallel machinesStatistica Neerlandica10.1111/j.1467-9574.1990.tb01276.x44:3(115-123)Online publication date: 29-Apr-2008
https://doi.org/10.1111/j.1467-9574.1990.tb01276.x
Uzsoy RVelásquez J(2008)Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up timesComputers and Operations Research10.1016/j.cor.2006.10.00335:6(2018-2033)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.cor.2006.10.003
Bonifaci VKorteweg PMarchetti-Spaccamela AStougie L(2008)Minimizing Average Flow Time in Sensor Data GatheringAlgorithmic Aspects of Wireless Sensor Networks10.1007/978-3-540-92862-1_3(18-29)Online publication date: 14-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-92862-1_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents