A new lower bound for the job-shop scheduling problem

DOI10.1016/0377-2217(93)90174-LzbMath0778.90022OpenAlexW2030592748MaRDI QIDQ2366077

Bernd Jurisch, Peter Brucker

Publication date: 29 June 1993

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

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90174-l

zbMATH Keywords

shortest pathlower boundsjob-shop schedulingobstaclesbranch-and- bound algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

A branch and bound algorithm for the job-shop scheduling problem, Application of quantum approximate optimization algorithm to job shop scheduling problem, The complexity of two-job shop problems with multi-purpose unrelated machines., Lower bounds for the job-shop scheduling problem on multi-purpose machines, Resource-constrained project scheduling: Notation, classification, models, and methods, The job shop scheduling problem: Conventional and new solution techniques, Modelling and heuristics of FMS scheduling with multiple objectives

Cites Work

• An efficient algorithm for the job-shop problem with two jobs
• Minimizing maximum lateness in a two-machine unit-time job shop
• Job-shop scheduling with multi-purpose machines
• The complexity of shop-scheduling problems with two or three jobs
• Benchmarks for basic scheduling problems
• Optimal two- and three-stage production schedules with setup times included
• 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
• Computational Complexity of Discrete Optimization Problems
• A Geometric Model and a Graphical Algorithm for a Sequencing Problem