A branch and bound algorithm for the job-shop scheduling problem

DOI10.1016/0166-218X(94)90204-6zbMath0802.90057MaRDI QIDQ1327223

Bernd Jurisch, Bernd Sievers, Peter Brucker

Publication date: 18 July 1994

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

zbMATH Keywords

branch-and-boundjob-shop scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A branch and bound algorithm for the job-shop scheduling problem, A multi-objective memetic algorithm for the job-shop scheduling problem, Applying tabu search to the job-shop scheduling problem, The job-shop problem and immediate selection, Distributionally robust single machine scheduling with the total tardiness criterion, Evolution based learning in a job shop scheduling environment, Dynamic resource allocation: a flexible and tractable modeling framework, Permutation-induced acyclic networks for the job shop scheduling problem, Evaluating topological ordering in directed acyclic graphs, Solving the job-shop scheduling problem optimally by dynamic programming, A branch \(\&\) bound algorithm for the open-shop problem, Simplifying dispatching rules in genetic programming for dynamic job shop scheduling, A neighborhood for complex job shop scheduling problems with regular objectives, Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors, Look ahead job demanding for improving job shop performance, Depth-first heuristic search for the job shop scheduling problem, A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags, A branch \(\&\) bound method for the general-shop problem with sequence dependent setup-times, New single machine and job-shop scheduling problems with availability constraints, A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Job-shop scheduling: Computational study of local search and large-step optimization methods, Immersed NURBS for CFD Applications, Scheduling of computational processes in real-time distributed systems with uncertain task execution times, Novel model and solution method for flexible job shop scheduling problem with batch processing machines, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis, An agent-based parallel approach for the job shop scheduling problem with genetic algorithms, A repairing technique for the local search of the job-shop problem., Study on constraint scheduling algorithm for job shop problems with multiple constraint machines, A branch and bound method for the job-shop problem with sequence-dependent setup times, A general system for heuristic minimization of convex functions over non-convex sets, Mixed multigraph approach to scheduling jobs on machines of different types^∗, A new approach to computing optimal schedules for the job-shop scheduling problem, No-wait job shop scheduling: tabu search and complexity of subproblems, An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling, Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times, A competent memetic algorithm for complex scheduling, Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments, Scheduling and constraint propagation, A hybrid genetic algorithm for the job shop scheduling problem, Solving the open shop scheduling problem, Jackson's pseudo-preemptive schedule and cumulative scheduling problems, Tabu search algorithms for job-shop problems with a single transport robot, Unnamed Item, Maximization of solution flexibility for robust shop scheduling, An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach, Local search algorithms for a single-machine scheduling problem with positive and negative time-lags, Nested partitions for the large-scale extended job shop scheduling problem, Alternative graph formulation for solving complex factory-scheduling problems, Jackson's semi-preemptive scheduling on a single machine, Lower bounds for the job-shop scheduling problem on multi-purpose machines, Resource-constrained project scheduling: Notation, classification, models, and methods, Deterministic job-shop scheduling: Past, present and future, Hybrid rollout approaches for the job shop scheduling problem, A discrete firefly algorithm for solving the flexible job-shop scheduling problem in a make-to-order manufacturing system, Two branch and bound algorithms for the permutation flow shop problem, The job shop scheduling problem: Conventional and new solution techniques, Measures of subproblem criticality in decomposition algorithms for shop scheduling, A new hybrid parallel genetic algorithm for the job‐shop scheduling problem, Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties, Decomposition methods for reentrant flow shops with sequence-dependent setup times, A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags, Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem, Constraint propagation techniques for the disjunctive scheduling problem, Applying machine based decomposition in 2-machine flow shops, The nonpermutation flowshop scheduling problem: adjustment and bounding procedures, Job-shop scheduling with blocking and no-wait constraints, Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems, An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Decomposition methods for large job shops, A tabu search algorithm for scheduling a single robot in a job-shop environment, Tabu search for the job-shop scheduling problem with multi-purpose machines, A tabu search approach to machine scheduling, A branch and bound to minimize the number of late jobs on a single machine with release time constraints

Uses Software

• JOBSHOP

Cites Work

• Unnamed Item
• A practical use of Jackson's preemptive schedule for solving the job shop problem
• A block approach for single-machine scheduling with release dates and due dates
• The one-machine sequencing problem
• A branch and bound algorithm for the job-shop scheduling problem
• A new lower bound for the job-shop scheduling problem
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• An Algorithm for Solving the Job-Shop Problem
• Job Shop Scheduling by Simulated Annealing
• A Computational Study of the Job-Shop Scheduling Problem
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness