The job shop scheduling problem: Conventional and new solution techniques

DOI10.1016/0377-2217(95)00362-2zbMath0980.90024OpenAlexW2162535720WikidataQ57387872 ScholiaQ57387872MaRDI QIDQ1268188

Wolfgang Domschke, Erwin Pesch, Jacek Błażewicz

Publication date: 18 October 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00362-2

zbMATH Keywords

surveyschedulingjob shopjob shop problemsolution techniques

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (74)

A novel threshold accepting meta-heuristic for the job-shop scheduling problem ⋮ A hybrid heuristic to solve the parallel machines job-shop scheduling problem ⋮ Heuristics for scheduling with inventory: Dynamic focus via constraint criticality ⋮ Job-shop production scheduling with reverse flows ⋮ A survey of job shop scheduling problem: the types and models ⋮ A very fast TS/SA algorithm for the job shop scheduling problem ⋮ A machine-order search space for job-shop scheduling problems ⋮ Path-relinking tabu search for the multi-objective flexible job shop scheduling problem ⋮ A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem ⋮ Scheduling the truckload operations in automatic warehouses ⋮ A multi-objective particle swarm for a flow shop scheduling problem ⋮ A neighborhood for complex job shop scheduling problems with regular objectives ⋮ Depth-first heuristic search for the job shop scheduling problem ⋮ Optimal makespan scheduling with given bounds of processing times ⋮ A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem ⋮ An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning ⋮ Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time ⋮ A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective ⋮ Immersed NURBS for CFD Applications ⋮ A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem ⋮ Sensitivity analysis of a fuzzy multiobjective scheduling problem ⋮ Mathematical modelling and heuristic approaches to job-shop scheduling problem with conveyor-based continuous flow transporters ⋮ Pattern mining‐based pruning strategies in stochastic local searches for scheduling problems ⋮ Flexible job-shop scheduling with transportation resources ⋮ An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents ⋮ A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems ⋮ Application of quantum approximate optimization algorithm to job shop scheduling problem ⋮ Two-machine job-shop scheduling with one joint job ⋮ Firefly-Inspired Algorithm for Job Shop Scheduling ⋮ Genetic algorithm modification for production scheduling ⋮ A repairing technique for the local search of the job-shop problem. ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ Multiobjective order assignment optimization in a global multiple-factory environment ⋮ An efficient genetic algorithm for job shop scheduling with tardiness objectives. ⋮ A Hybrid Constraint Programming / Local Search Approach to the Job-Shop Scheduling Problem ⋮ Bid generation and evaluation for MANPro-based real time scheduling ⋮ 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 ⋮ Fuzzy job shop scheduling with lot-sizing ⋮ Ant colony optimization combined with taboo search for the job shop scheduling problem ⋮ An advanced tabu search algorithm for the job shop problem ⋮ Efficient primal heuristic updates for the blocking job shop problem ⋮ Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal ⋮ Multiobjective optimization for complex flexible job-shop scheduling problems ⋮ Open shop cyclic scheduling ⋮ No-wait job shop scheduling: tabu search and complexity of subproblems ⋮ A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints ⋮ 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 review of exact solution methods for the non-preemptive multiprocessor flowshop problem ⋮ Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem ⋮ Tabu search algorithms for job-shop problems with a single transport robot ⋮ Solving job shop scheduling problems utilizing the properties of backbone and ``big valley ⋮ Time-optimal coordination of flexible manufacturing systems using deterministic finite automata and mixed integer linear programming ⋮ Competitive analysis for the on-line truck transportation problem ⋮ An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach ⋮ Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling ⋮ Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound ⋮ Some new results on simulated annealing applied to the job shop scheduling problem ⋮ Scheduling production tasks in a two-stage FMS ⋮ 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 ⋮ Complete local search with limited memory algorithm for no-wait job shops to minimize makespan ⋮ Lot sizing and scheduling -- survey and extensions ⋮ Modelling and heuristics of FMS scheduling with multiple objectives ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing ⋮ Applying machine based decomposition in 2-machine flow shops ⋮ Packing-based branch-and-bound for discrete malleable task scheduling ⋮ Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic ⋮ Genetic multi-criteria approach to flexible line scheduling ⋮ Problem difficulty for tabu search in job-shop scheduling ⋮ A knowledge-based evolutionary strategy for scheduling problems with bottlenecks

Uses Software

• CHIP
• Genocop
• JOBSHOP
• Tabu search

Cites Work

• Mathematical programming formulations for machine scheduling: A survey
• Some efficient heuristic methods for the flow shop sequencing problem
• Comments on Mohr and Henderson's path consistency algorithm
• A practical use of Jackson's preemptive schedule for solving the job shop problem
• A note on minimizing maximum lateness in a one-machine sequencing problem with release dates
• A block approach for single-machine scheduling with release dates and due dates
• Scheduling jobs with release dates and tails on identical machines to minimize the makespan
• Network-based heuristics for constraint-satisfaction problems
• An efficient algorithm for the job-shop problem with two jobs
• How easy is local search?
• A survey of priority rule-based scheduling
• A new heuristic method for the flow shop sequencing problem
• An adaptive branching rule for the permutation flow-shop problem
• The one-machine sequencing problem
• Surrogate duality relaxation for job shop scheduling
• The complexity of shop-scheduling problems with two or three jobs
• Permutation vs. non-permutation flow shop schedules
• A generic arc-consistency algorithm and its specializations
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Consistency in networks of relations
• A computational study of constraint satisfaction for multiple capacitated job shop scheduling
• Genetic local search in combinatorial optimization
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• A branch and bound algorithm for the job-shop scheduling problem
• Unrelated parallel machine scheduling using local search
• Adjustment of heads and tails for the job-shop problem
• A decision support system for the resource constrained project scheduling problem
• Applying tabu search with influential diversification to multiprocessor scheduling
• A genetic algorithm for the job shop problem
• Evolution based learning in a job shop scheduling environment
• Effective job shop scheduling through active chain manipulation
• TSP ejection chains
• Job-shop scheduling: Computational study of local search and large-step optimization methods
• Genetic algorithms: Foundations and applications
• Networks of constraints: Fundamental properties and applications to picture processing
• NP-hardness of shop-scheduling problems with three jobs
• A generalized permutation approach to job shop scheduling with genetic algorithms
• A new heuristic for the n-job, M-machine flow-shop 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
• Sequencing theory
• Optimal two- and three-stage production schedules with setup times included
• Mathematical Modeling of Scheduling Problems
• Simulation studies in JIT production
• A concise survey of efficiently solvable special cases of the permutation flow-shop problem
• A general search sequencing rule for job shop sequencing
• On the facial structure of scheduling polyhedra
• Scheduling the General Job-Shop
• The Three-Machine No-Wait Flow Shop is NP-Complete
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• DETERMINISTIC SCHEDULING IN COMPUTER SYSTEMS: A SURVEY
• On the Development of a Mixed-Integer Linear Programming Model for the Flowshop Sequencing Problem
• An Algorithm for Solving the Job-Shop Problem
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
• Computer-Aided complexity classification of combinational problems
• An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem
• The Lessons of Flowshop Scheduling Research
• Job Shop Scheduling by Simulated Annealing
• Tabu Search—Part I
• Tabu Search—Part II
• New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
• A Computational Study of the Job-Shop Scheduling Problem
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• A Comparative Study of Flow-Shop Algorithms
• On general routing problems
• A Survey of Scheduling Rules
• A General Bounding Scheme for the Permutation Flow-Shop Problem
• Flowshop and Jobshop Schedules: Complexity and Approximation
• Technical Note—Three-Stage Flow-Shops with Recessive Second Stage
• An Evaluation of Flow Shop Sequencing Heuristics
• Job-Shop Scheduling by Implicit Enumeration
• Technical Note—Improved Dominance Conditions for the Three-Machine Flowshop Scheduling Problem
• Technical Note—Dominance Conditions for the Three-Machine Flow-Shop Problem
• The Complexity of Flowshop and Jobshop Scheduling
• Computational Complexity of Discrete Optimization Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
• A Computational Study of Local Search Algorithms for Job Shop Scheduling
• Fast Clustering Algorithms
• A Fast Taboo Search Algorithm for the Job Shop Problem
• A new approach to computing optimal schedules for the job-shop scheduling problem
• A modified shifting bottleneck procedure for job-shop scheduling
• The NP-completeness column: An ongoing guide
• The One-Machine Problem with Delayed Precedence Constraints and its Use in Job Shop Scheduling
• Problem and Heuristic Space Search Strategies for Job Shop Scheduling
• The Schedule-Sequencing Problem
• Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem
• Equation of State Calculations by Fast Computing Machines
• A Branch-Bound Solution to the General Scheduling Problem
• Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm
• A Generalized Machine-Scheduling Algorithm
• The Sequencing Problem
• A Heuristic Algorithm for the n Job, m Machine Sequencing Problem
• Review of sequencing research
• A Direct Search Method to Locate Negative Cycles in a Graph
• Elimination methods in them ×n sequencing problem
• Algorithms for Solving Production-Scheduling Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The job shop scheduling problem: Conventional and new solution techniques