A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

DOI10.1016/S0166-218X(99)00015-3zbMath0932.68006MaRDI QIDQ1293191

Peter Brucker, Thomas Hilbig, Johann L. Hurink

Publication date: 28 June 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

metra potential method

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Scatter search with path relinking for the job shop with time lags and setup times, A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags, Minimum equivalent precedence relation systems, Weight-based heuristics for constraint satisfaction and combinatorial optimization problems, Production scheduling with alternative process plans, Four decades of research on the open-shop scheduling problem to minimize the makespan, A memetic algorithm for the job-shop with time-lags, Time symmetry of resource constrained project scheduling with general temporal constraints and take-give resources, Minimizing flowtime for paired tasks, Unnamed Item, Local search algorithms for a single-machine scheduling problem with positive and negative time-lags, An Optimal Constraint Programming Approach to the Open-Shop Problem, Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems, Improved formulations and new valid inequalities for a hybrid flow shop problem with time-varying resources and chaining time-lag

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The one-machine sequencing problem
• Job-shop scheduling with multi-purpose machines
• Scheduling multiprocessor tasks on three dedicated processors
• A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations
• A branch and bound algorithm for the job-shop scheduling problem
• Heuristics for scheduling resource-constrained projects in MPM networks
• The job-shop problem and immediate selection
• One-machine generalized precedence constrained scheduling problems
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• A branch \(\&\) bound algorithm for the open-shop problem
• Benchmarks for basic scheduling problems
• An Algorithm for Solving the Job-Shop Problem
• The Analysis of Activity Networks Under Generalized Precedence Relations (GPRs)
• On the Complexity of Scheduling with Batch Setup Times
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling