Adjustment of heads and tails for the job-shop problem

DOI10.1016/0377-2217(94)90379-4zbMath0812.90063OpenAlexW2020459421MaRDI QIDQ1341994

Jacques Carlier, Éric Pinson

Publication date: 11 January 1995

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

Full work available at URL: https://doi.org/10.1016/0377-2217(94)90379-4

zbMATH Keywords

branch-and-boundlower boundjob-shopimmediate selections of disjunctive constraints

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Constraint programming and operations research ⋮ Energetic reasoning revisited: Application to parallel machine scheduling ⋮ A branch and bound algorithm for scheduling trains in a railway network ⋮ Heuristics for scheduling with inventory: Dynamic focus via constraint criticality ⋮ Extension of \(O(n \log n)\) filtering algorithms for the unary resource constraint to optional activities ⋮ Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search ⋮ Optimal scheduling of a two-stage hybrid flow shop ⋮ An efficient algorithm for the job-shop problem with two jobs ⋮ Unnamed Item ⋮ A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags ⋮ Arc-B-consistency of the inter-distance constraint ⋮ New single machine and job-shop scheduling problems with availability constraints ⋮ An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem ⋮ Improving the preemptive bound for the single machine dynamic maximum lateness problem ⋮ Application of quantum approximate optimization algorithm to job shop scheduling problem ⋮ Resource leveling in a machine environment ⋮ Strong polynomiality of resource constraint propagation ⋮ Dominance rules in combinatorial optimization problems ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the resource constrained project scheduling problem ⋮ Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics ⋮ A constraint programming approach for the resource-constrained project scheduling problem ⋮ A new approach to computing optimal schedules for the job-shop scheduling problem ⋮ Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times ⋮ A competent memetic algorithm for complex scheduling ⋮ Two-stage hybrid flow shop with precedence constraints and parallel machines at second stage ⋮ Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments ⋮ Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem ⋮ Scheduling and constraint propagation ⋮ A heuristic for scheduling general job shops to minimize maximum lateness ⋮ Solving the open shop scheduling problem ⋮ Jackson's pseudo-preemptive schedule and cumulative scheduling problems ⋮ Local adjustments: A general algorithm ⋮ A computational study of the permutation flow shop problem based on a tight lower bound ⋮ Alternative graph formulation for solving complex factory-scheduling problems ⋮ Jackson's semi-preemptive scheduling on a single machine ⋮ Solving an integrated job-shop problem with human resource constraints ⋮ Deterministic job-shop scheduling: Past, present and future ⋮ An Optimal Constraint Programming Approach to the Open-Shop Problem ⋮ Using short-term memory to minimize the weighted number of late jobs on a single machine. ⋮ Two branch and bound algorithms for the permutation flow shop problem ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties ⋮ Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates ⋮ Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case ⋮ Neighborhood singleton consistencies ⋮ Reduction of job-shop problems to flow-shop problems with precedence constraints ⋮ Constraint-directed techniques for scheduling alternative activities ⋮ Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem ⋮ Constraint propagation techniques for the disjunctive scheduling problem ⋮ Constraint-Level Advice for Shaving ⋮ The nonpermutation flowshop scheduling problem: adjustment and bounding procedures ⋮ Job-shop scheduling with blocking and no-wait constraints ⋮ The disjunctive graph machine representation of the job shop scheduling problem ⋮ On not-first/not-last conditions in disjunctive scheduling ⋮ Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems ⋮ A quadratic edge-finding filtering algorithm for cumulative resource constraints ⋮ Local search with constraint propagation and conflict-based heuristics ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A practical use of Jackson's preemptive schedule for solving the job shop problem
• An adaptive branching rule for the permutation flow-shop problem
• The one-machine sequencing problem
• The job-shop problem and immediate selection
• Scheduling the General Job-Shop
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• An Algorithm for Solving the Job-Shop Problem
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Minimizing maximum lateness on one machine: computational experience and some applications
• Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm