An Algorithm for Solving the Job-Shop Problem

DOI10.1287/MNSC.35.2.164zbMath0677.90036OpenAlexW2130272456MaRDI QIDQ3833853

Éric Pinson, Jacques Carlier

Publication date: 1989

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.35.2.164

zbMATH Keywords

branch and boundmakespanjob-shopdisjunctive graphone-machine scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Data structures (68P05)

Related Items (only showing first 100 items - show all)

Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search ⋮ A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times ⋮ An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning ⋮ Immersed NURBS for CFD Applications ⋮ Novel model and solution method for flexible job shop scheduling problem with batch processing machines ⋮ A spatial pyramid pooling-based deep reinforcement learning model for dynamic job-shop scheduling problem ⋮ An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents ⋮ Efficient algorithms for flexible job shop scheduling with parallel machines ⋮ Two-machine job-shop scheduling with one joint job ⋮ Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem ⋮ Study on constraint scheduling algorithm for job shop problems with multiple constraint machines ⋮ Unnamed Item ⋮ Mixed multigraph approach to scheduling jobs on machines of different types^∗ ⋮ A Column Generation Model for a Scheduling Problem with Maintenance Constraints ⋮ Integrating operations research in constraint programming ⋮ A new approach to computing optimal schedules for the job-shop scheduling problem ⋮ Integrating operations research in constraint programming ⋮ An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling ⋮ Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments ⋮ A dynamic job shop scheduling framework: a backward approach ⋮ A game-theoretic control approach for job shops in the presence of disruptions ⋮ Scheduling with tails and deadlines ⋮ Solving the open shop scheduling problem ⋮ Planning as heuristic search ⋮ Minimizing L _max for large-scale, job-shop scheduling problems ⋮ Planning and control in artificial intelligence: A unifying perspective ⋮ Scheduling jobshops with some identical or similar jobs ⋮ A modified shifting bottleneck procedure for job-shop scheduling ⋮ Complete Complexity Classification of Short Shop Scheduling ⋮ Measures of subproblem criticality in decomposition algorithms for shop scheduling ⋮ Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties ⋮ Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem ⋮ A genetic algorithm applied to a classic job-shop scheduling problem ⋮ Applying machine based decomposition in 2-machine flow shops ⋮ Scheduling larger job shops: a decomposition approach ⋮ A branch and bound algorithm for the job-shop scheduling problem ⋮ Constraint programming and operations research ⋮ An improved shifting bottleneck procedure for the job shop scheduling problem ⋮ A new lower bound for the job-shop scheduling problem ⋮ Benchmarks for basic scheduling problems ⋮ Applying tabu search to the job-shop scheduling problem ⋮ The job-shop problem and immediate selection ⋮ An efficient heuristic based on machine workload for the flowshop scheduling problem with setup and removal ⋮ A robust approach for the single machine scheduling problem ⋮ Energetic reasoning revisited: Application to parallel machine scheduling ⋮ A branch and bound algorithm for scheduling trains in a railway network ⋮ Job-shop scheduling with convex models of operations ⋮ Adjustment of heads and tails for the job-shop problem ⋮ A decision support system for the resource constrained project scheduling problem ⋮ Effective job shop scheduling through active chain manipulation ⋮ Dynamic resource allocation: a flexible and tractable modeling framework ⋮ Permutation-induced acyclic networks for the job shop scheduling problem ⋮ Type-2 integrated process-planning and scheduling problem: reformulation and solution algorithms ⋮ An \(R||C_{\max}\) quantum scheduling algorithm ⋮ A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: the case of job shop scheduling ⋮ An effective architecture for learning and evolving flexible job-shop schedules ⋮ An effective lower bound on \(L_{\max}\) in a worker-constrained job shop ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ A branch \(\&\) bound algorithm for the open-shop problem ⋮ An effective new island model genetic algorithm for job shop scheduling problem ⋮ Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements ⋮ Theoretical expectation versus practical performance of Jackson's heuristic ⋮ 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 fluid approach to large volume job shop scheduling ⋮ 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 ⋮ Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach ⋮ 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 ⋮ An alternative framework to Lagrangian relaxation approach for job shop scheduling. ⋮ A branch and cut algorithm for resource-constrained project scheduling problem subject to nonrenewable resources with pre-scheduled procurement ⋮ An agent-based parallel approach for the job shop scheduling problem with genetic algorithms ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A complete 4-parametric complexity classification of short shop scheduling problems ⋮ Project scheduling with flexible resources: formulation and inequalities ⋮ An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem ⋮ Branch and bound algorithms for resource constrained project scheduling problem subject to nonrenewable resources with prescheduled procurement ⋮ A tabu search method guided by shifting bottleneck for the job shop scheduling problem ⋮ Branching and pruning: An optimal temporal POCL planner based on constraint programming ⋮ FMS scheduling based on timed Petri net model and reactive graph search ⋮ Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics ⋮ A branch and bound method for the job-shop problem with sequence-dependent setup times ⋮ Ant colony optimization combined with taboo search for the job shop scheduling problem ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Resource tardiness weighted cost minimization in project scheduling ⋮ A prediction based iterative decomposition algorithm for scheduling large-scale job shops ⋮ A filter-and-fan approach to the job shop scheduling problem ⋮ One-machine rescheduling heuristics with efficiency and stability as criteria ⋮ Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times ⋮ Scheduling and constraint propagation ⋮ A hybrid genetic algorithm for the job shop scheduling problem ⋮ A heuristic for scheduling general job shops to minimize maximum lateness ⋮ Jackson's pseudo-preemptive schedule and cumulative scheduling problems ⋮ Local adjustments: A general algorithm ⋮ Nested partitions for the large-scale extended job shop scheduling problem ⋮ Jackson's semi-preemptive scheduling on a single machine ⋮ Insertion techniques for the heuristic solution of the job shop problem ⋮ Two simulated annealing-based heuristics for the job shop scheduling problem ⋮ Resource-constrained project scheduling: Notation, classification, models, and methods

This page was built for publication: An Algorithm for Solving the Job-Shop Problem