Computer-Aided complexity classification of combinational problems

DOI10.1145/358690.363066MaRDI QIDQ3953190zbMATH OpenOpenAlexFDO

Authors B. J. Lageweg, Alexander H. G. Rinnooy Kan, Jan Karel Lenstra, Eugene L. Lawler

Publication date 1982

Published in Communications of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/358690.363066

zbMATH Keywords

combinatorial optimizationNP-hardnesspolynomial algorithmscheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• scientific article; zbMATH DE number 3891075
• scientific article; zbMATH DE number 3860868
• Computational complexity of problems in classification according to a relation matrix
• scientific article; zbMATH DE number 1107550
• scientific article; zbMATH DE number 4031379

Cited in

(13)

• The job shop scheduling problem: Conventional and new solution techniques
• Problems, models and complexity. I: Theory
• Machine scheduling with earliness, tardiness and non-execution penalties
• Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times
• Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time
• Scheduling identical jobs on uniform parallel machines
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• Developing feasible and optimal schedules of jobs on one machine
• scientific article; zbMATH DE number 1305102 (Why is no real title available?)
• SCHEDULING INTERVAL ORDERS IN PARALLEL
• Parameterized algorithms and complexity for scheduling with precedence constraints and time windows
• New directions in scheduling theory
• A classification scheme for vehicle routing and scheduling problems

This page was built for publication: Computer-Aided complexity classification of combinational problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3953190)