The time dependent machine makespan problem is strongly NP-complete

DOI10.1016/S0305-0548(98)00093-8MaRDI QIDQ1304510zbMATH OpenOpenAlexFDO

Authors T. C. Edwin Cheng, Q. Ding

Publication date 22 September 1999

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0305-0548(98)00093-8

zbMATH Keywords

sequencingtime dependence

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• The complexity of scheduling starting time dependent tasks with release times
• Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine
• The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times
• scientific article; zbMATH DE number 1187294

Cited in

(9)

• A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time
• The complexity of scheduling starting time dependent tasks with release times
• A note on proving the strong NP-hardness of some scheduling problems with start time dependent job processing times
• A time-dependent multiple criteria single-machine scheduling problem
• Single machine scheduling with step-deteriorating processing times
• A review of four decades of time-dependent scheduling: main results, new topics, and open problems
• Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine
• ``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
• A concise survey of scheduling with time-dependent processing times

This page was built for publication: The time dependent machine makespan problem is strongly NP-complete

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