The local-global conjecture for scheduling with non-linear cost

DOI10.1007/s10951-015-0466-5zbMath1376.90022arXiv1304.6188OpenAlexW2257558496WikidataQ122979004 ScholiaQ122979004MaRDI QIDQ2400434

Christoph Dürr, Nikhil Bansal, Nguyen Kim Thang, Oscar C. Vásquez

Publication date: 1 September 2017

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6188

zbMATH Keywords

schedulingsingle machinenonlinear cost functionpruning rulesalgorithm A*

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

On Submodular Search and Machine Scheduling ⋮ The TV advertisements scheduling problem ⋮ A novel MILP model for \(N\)-vehicle exploration problem

Cites Work

• Unnamed Item
• Unnamed Item
• Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
• Decomposition in single-machine scheduling
• An improved precedence rule for single machine sequencing problems with quadratic penalty
• For the airplane refueling problem local precedence implies global precedence
• On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
• A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
• Universal Sequencing on a Single Machine
• Note—A Node Elimination Procedure for Townsend's Algorithm for Solving the Single Machine Quadratic Penalty Function Scheduling Problem
• The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution
• An experimental and analytical study of order constraints for single machine scheduling with quadratic cost
• Numerical Methods for Single Machine Scheduling with Non-linear Cost Functions to Minimize Total Cost
• Dual Techniques for Scheduling on a Machine with Varying Speed