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 optimizationschedulingNP-hardnesspolynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) 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

(12)

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

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)