Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard.

DOI10.1016/S0020-0190(01)00143-0zbMath1051.68082OpenAlexW2013271485WikidataQ127251377 ScholiaQ127251377MaRDI QIDQ1603395

Guohua Wan, Benjamin P.-C. Yen, Chung-Lun Li

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00143-0

zbMATH Keywords

SchedulingComputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Scheduling with controllable processing times and compression costs using population-based heuristics ⋮ Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ A survey of scheduling with controllable processing times ⋮ Considering manufacturing cost and scheduling performance on a CNC turning machine ⋮ Batch scheduling of identical jobs with controllable processing times ⋮ Controllable processing times in project and production management: analysing the trade-off between processing times and the amount of resources ⋮ Pre-emptive scheduling problems with controllable processing times ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Scheduling with controllable release dates and processing times: total completion time minimization ⋮ A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates ⋮ The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times ⋮ Complexity of a scheduling problem with controllable processing times ⋮ Scheduling two agents with controllable processing times ⋮ Positive half-products and scheduling with controllable processing times ⋮ Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling ⋮ Multicriteria scheduling ⋮ Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Cites Work

• A survey of results for sequencing problems with controllable processing times
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine