Strong NP-hardness of scheduling problems with learning or aging effect

DOI10.1007/s10479-013-1364-xzbMath1309.90026OpenAlexW1966570709MaRDI QIDQ363599

Mikhail Y. Kovalyov, Adam Janiak, Maciej Lichtenstein

Publication date: 3 September 2013

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-013-1364-x

zbMATH Keywords

computational complexityschedulingsingle machineflowshoplearning effectaging effect

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Scheduling problem in seru production system considering DeJong's learning effect and job splitting ⋮ Research on permutation flow shop scheduling problems with general position-dependent learning effects

Cites Work

• On single processor scheduling problems with learning dependent on the number of processed jobs
• The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect
• Single-machine scheduling problems with time and position dependent processing times
• Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects
• Single-machine group scheduling with time-dependent learning effect and position-based setup time learning effect
• Scheduling problems with position dependent job processing times: computational complexity results
• Single-machine scheduling with both deterioration and learning effects