The time dependent machine makespan problem is strongly NP-complete

DOI10.1016/S0305-0548(98)00093-8zbMath0932.90013OpenAlexW2022314204MaRDI QIDQ1304510

Qing Ding, Cheng, T. C. Edwin

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)

Related Items

A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time, A concise survey of scheduling with time-dependent processing times, Single machine scheduling with step-deteriorating processing times, A time-dependent multiple criteria single-machine scheduling problem, 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