Solving the job-shop scheduling problem optimally by dynamic programming

DOI10.1016/j.cor.2012.02.024zbMath1349.90348OpenAlexW2014366273MaRDI QIDQ339631

Jelke J. van Hoorn, Gerrit T. Timmer, Joaquim A. S. Gromicho, Francisco Saldanha-Da-gama

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.02.024

zbMATH Keywords

dynamic programmingjob-shop schedulingcomplexity analysis

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (12)

Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm ⋮ Corrigendum to: ``Solving the job-shop scheduling problem optimally by dynamic programming ⋮ Deep policy dynamic programming for vehicle routing problems ⋮ A modified genetic algorithm with fuzzy roulette wheel selection for job-shop scheduling problems ⋮ A hybrid multi-objective approach for real-time flexible production scheduling and rescheduling under dynamic environment in Industry 4.0 context ⋮ Efficient algorithms for flexible job shop scheduling with parallel machines ⋮ Genetic algorithm modification for production scheduling ⋮ Improved bounded dynamic programming algorithm for solving the blocking flow shop problem ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ Dynamic programming approach for solving the open shop problem ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights ⋮ On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A filter-and-fan approach to the job shop scheduling problem
• A branch and bound algorithm for the job-shop scheduling problem
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• A genetic algorithm for the job shop problem
• Evolution based learning in a job shop scheduling environment
• Restricted dynamic programming: a flexible framework for solving realistic VRPs
• Two simulated annealing-based heuristics for the job shop scheduling problem
• Deterministic job-shop scheduling: Past, present and future
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• A very fast TS/SA algorithm for the job shop scheduling problem
• Open problems around exact algorithms
• Makespan minimization in job shops
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• An Algorithm for Solving the Job-Shop Problem
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• Job Shop Scheduling by Simulated Annealing
• A Computational Study of the Job-Shop Scheduling Problem
• Job-Shop Scheduling by Implicit Enumeration
• Computational Complexity of Discrete Optimization Problems
• Improved Approximation Algorithms for Shop Scheduling Problems
• Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
• A Fast Taboo Search Algorithm for the Job Shop Problem
• A new approach to computing optimal schedules for the job-shop scheduling problem

This page was built for publication: Solving the job-shop scheduling problem optimally by dynamic programming