PaperlayerView exact revision on arXiv

Source-linked AI summary

Novel Iterative Construction Methods for the Blocking Job Shop Scheduling Problem

Adel Dabah, Karima Rihane, Hocine Saadi, Andreas Herten, Farouk Benslimane, Mohammed Lamine Bahmani, Abdelhakim Aitzai

arXiv:2609.16007v1cs.DC

TL;DR

The BJSSP is difficult because zero-buffer constraints reduce feasible search and couple consecutive machine operations. The paper proposes BS-ICH, PMS-BS, and GPU-accelerated G-PMS-BS to construct feasible schedules while expanding search in parallel. Across Lawrence and Taillard benchmarks, the GPU approach reports a 44× speedup and new best-known results, including improvements of up to 13% on the largest instances.

  • Problem

    Zero-buffer BJSSP creates strong machine coupling and causes metaheuristics to explore many infeasible solutions with costly feasibility recovery.

  • Method

    The paper develops BS-ICH, PMS-BS, and G-PMS-BS, combining k-best feasible partial schedules, machine-biased parallel diversification, and GPU beam expansion.

  • Results

    G-PMS-BS delivers a 44× GPU speedup and sets new best-known results on 18/20 large Lawrence instances and 77/80 Taillard instances.

  • Takeaways & Limitations

    Construction-based search combines guaranteed feasibility, beam diversity, and massive parallelism for large-scale BJSSP scheduling.

Abstract

from arXiv · show

The Blocking Job-Shop Scheduling Problem (BJSSP) arises in modern and complex manufacturing, production, logistics, and service where no intermediate storage is allowed between consecutive operations. This creates a significant challenge for meta-heuristics due to the low ratio of feasible to explored solutions when solving the problem. To address this problem efficiently, we propose three new beam-search-based heuristics: the Beam Search Iterative Construction Heuristic (BS-ICH), its CPU-parallel extension Parallel Multi-Strategy Beam Search (PMS-BS), and a GPU-accelerated variants G-PMS-BS. BS-ICH constructs feasible schedules by iteratively extending partial solutions, while maintaining a beam of width k to preserve multiple high-quality partial schedules. PMS-BS runs hundreds of parallel BS-ICH instances with machine-biased diversity to expand the search space and escape local optima. G-PMS-BS offloads the beam expansion onto massively parallel GPU hardware using a two-phase kernel architecture that separates lightweight scoring from targeted state reconstruction, enabling scaling to instances with 2,000 operations. A hybrid CPU+GPU mode further exploits idle host cores for concurrent exploration, using load-balancing strategy to minimize synchronization overhead. G-PMS-BS achieves a 44x speedup over the CPU baseline. Experiments on all standard Lawrence and Taillard instances demonstrate that G-PMS-BS establishes new best-known results for 22 Lawrence benchmarks and 77 Taillard instances, with makespan reductions of up to 13% on the largest 100x20 instances.

I. INTRODUCTION

The BJSSP’s zero-buffer constraints intensify search difficulty by coupling machines and making feasibility recovery costly. The paper proposes beam-search heuristics that construct feasible schedules while combining beam diversity, parallel exploration, and GPU acceleration.

  • I. INTRODUCTION: Zero-buffer blocking couples machines because completed operations remain on their current machines until successors can begin.This coupling exacerbates search-space explosion and invalidates heuristic rules designed for classical JSSP.
  • I. INTRODUCTION: Existing metaheuristics often explore many infeasible solutions, require costly feasibility recovery, and demand extensive parameter tuning.Exact methods solve small instances optimally but scale poorly, while hybrid and learning-based methods increase algorithmic complexity as states and actions grow exponentially.
  • I. INTRODUCTION: PMS-BS runs multiple BS-ICH instances in parallel with machine-priority biases and random candidate injection to diversify exploration and escape local optima.The framework explicitly combines feasibility, parallelism, and diversification.
  • I. INTRODUCTION: BS-ICH maintains the k-best partial schedules at each construction step and directly constructs feasible schedules under blocking constraints.This balances feasibility and exploration without the recovery phases used by many metaheuristics.
  • I. INTRODUCTION: G-PMS-BS achieves a 44× speedup over the CPU baseline while scaling beam expansion to very large BJSSP instances.Its GPU implementation uses a two-phase kernel architecture, and the hybrid CPU+GPU mode exploits otherwise-idle host cores.

II. BLOCKING JOB SHOP SCHEDULING PROBLEM

The BJSSP extends job-shop scheduling with zero-buffer blocking, requiring operations to remain on machines until successors are ready. Its formulation combines precedence, machine-capacity, blocking, and alternative-order constraints, with makespan as the objective.

  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: Zero-buffer blocking requires an operation to remain on its current machine until its successor can start on the next machine.This creates implicit inter-machine dependencies and makes BJSSP more difficult than classical JSSP.
  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: Schedules must satisfy job precedence constraints and prevent overlapping operations assigned to the same machine.Precedence requires each operation to start after its predecessor finishes; machine capacity imposes an ordering between every pair sharing a machine.
  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: For a job’s final operation, completion time equals start time plus processing time.The successor-based blocking condition does not apply when no successor exists.
  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: The objective is to minimize makespan, defined as the time when the last operation finishes.
  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: The alternative graph represents operations and dummy start/end nodes, fixed precedence arcs, and alternative pairs encoding processing order between concurrent operations.
  • II. BLOCKING JOB SHOP SCHEDULING PROBLEM: The paper studies Blocking with Swap, where operations in a zero-length-cycle deadlock may move simultaneously to their respective next machines.This is more challenging than Blocking with No Swap, which treats swap-containing solutions as infeasible.

A. RELATED WORKS

Prior BJSSP research spans exact algorithms, constructive heuristics, metaheuristics, graph-based methods, parallel search, and learning-based approaches. These studies improve solution quality or scalability across different problem sizes and variants.

  • A. RELATED WORKS: Tabu search, geometric methods, and iterated greedy approaches address BJSSP variants including no-swap constraints and improve previously reported results.Reported tabu-search relative errors were 3%–9% against optimal solutions on 10×10 benchmarks.
  • A. RELATED WORKS: Constructive and graph-based methods include alternative-graph heuristics, branch-and-bound, rollout, and iterative flattening search for blocking and related scheduling variants.Mascis and Pacciarelli optimally solved all 10×10 instances using branch-and-bound built on their constructive heuristics.
  • A. RELATED WORKS: Parallel branch-and-bound methods exploit cluster, multicore CPU, and GPU architectures, achieving speedups of up to 100× in prior work.One parallel branch-and-bound approach reported optimal solutions for ten previously unsolved benchmark instances and improvements for 22 others.
  • A. RELATED WORKS: Recent learning-based work includes learned branching rules for branch-and-bound and reinforcement learning formulations of BJSSP as a Markov decision process.These approaches extend machine-learning techniques to small and medium BJSSP instances and scheduling decisions.

III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC

BS-ICH constructs feasible BJSSP schedules incrementally while retaining the K most promising partial schedules, balancing search diversity against runtime. Its fixed-width beam and machine-serialized expansion yield polynomial complexity, while machine selection can cause convergence to suboptimal schedules.

  • III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC: BS-ICH extends feasible partial schedules operation by operation, maintaining the K most promising candidates and pruning by partial makespan.The construction-based approach avoids generating infeasible schedules under blocking constraints.
  • III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC: K = 1 recovers greedy construction, whereas K ∈ [5, 20] empirically yields 5% −10% better makespans with moderate overhead.The beam width therefore provides a tunable trade-off between greedy construction and broader search.
  • III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC: BS-ICH has worst-case time complexity O(N · K · J log K), simplifying to O(N · K · J) when K is treated as a small constant.The algorithm considers feasible extensions on one selected machine and retains only the top K candidates.
  • III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC: Feasibility-preserving construction and machine-serialized expansion prevent backtracking and duplicate partial schedules, supporting scaling of later parallel variants to 2,000-operation instances.These design choices preserve the polynomial complexity foundation for PMS-BS and G-PMS-BS.
  • III. BEAM SEARCH ITERATIVE CONSTRUCTION HEURISTIC: Machine selection can drive BS-ICH toward a suboptimal schedule, motivating PMS-BS diversity strategies.The limitation arises because selecting one machine reduces explored branches and may prune potentially good solutions early.

IV. PARALLEL MULTI-STRATEGY BEAM SEARCH

PMS-BS addresses BS-ICH's convergence risk by running independent beam searches with distinct machine-priority biases and controlled randomness. The instances exchange the best makespan so they can prune partial schedules that cannot improve the global result.

  • IV. PARALLEL MULTI-STRATEGY BEAM SEARCH: PMS-BS launches L independent BS-ICH instances with distinct machine-priority biases and controlled randomness to improve diversity and avoid local optima.Each instance explores the search space independently rather than synchronizing its internal beam-search decisions.
  • IV. PARALLEL MULTI-STRATEGY BEAM SEARCH: The instances periodically exchange the best known makespan, enabling pruning of partial schedules whose estimated makespan exceeds the global best.This improves efficiency without requiring synchronization of the internal search logic.
  • IV. PARALLEL MULTI-STRATEGY BEAM SEARCH: Each strategy selects machines according to its bias, while the diversification probability ε injects randomness to prevent premature convergence.Priority functions steer instances toward different machine-usage profiles.

V. GPU-ACCELERATED PMS-BS (G-PMS-BS)

G-PMS-BS addresses the limited parallel throughput of multicore CPUs by mapping beam-search expansion and evaluation directly onto GPU hardware.

  • V. GPU-ACCELERATED PMS-BS (G-PMS-BS): G-PMS-BS maps beam expansion and candidate evaluation onto GPU hardware because CPU multicore throughput cannot sustain the large candidate volume produced by wide beams.The method targets iterations that may simulate hundreds of thousands of partial schedules.

A. GPU ARCHITECTURE

The GPU architecture combines many streaming multiprocessors with hierarchical memory to execute fine-grained parallel workloads. Resource balancing is needed to limit costly global-memory traffic.

  • A. GPU ARCHITECTURE: GPU execution distributes thread blocks across streaming multiprocessors, with warps of 32 threads executing the same instruction on different data.The architecture exposes massive fine-grained parallelism for beam-search workloads.
  • A. GPU ARCHITECTURE: Registers, shared memory, and global memory provide different latency and capacity levels, so the implementation balances resources to minimize global-memory traffic.Registers are fastest but limited, shared memory supports block-local sharing, and global memory offers the largest capacity.

B. G-PMS-BS AND MAPPING ON GPUS

G-PMS-BS maps beam expansion and evaluation onto GPUs through staged candidate processing, device-side selection, and survivor reconstruction. Profiling shows the GPU execution is dominated by scoring and reconstruction, with reconstruction limited by divergence and scattered memory access.

  • G-PMS-BS splits each beam-search iteration into candidate expansion and evaluation, device-side selection, and reconstruction of selected schedules.The design limits intermediate memory use by reconstructing only the globally selected candidates.
  • Each GPU thread evaluates candidate operations independently, while device-wide radix sorting selects the K globally best candidates across parent schedules.
  • The reconstruction kernel processes only survivors, replaying their scheduling decisions to build the next beam while preserving the original search behavior.
  • GPU profiling found scoring consumed 55.8% of GPU time, reconstruction 43.0%, and sorting 1.1%, with both kernels memory-bound.Reconstruction was additionally latency-bound by thread divergence and scattered global-memory accesses.

C. HYBRID CPU+GPU EXECUTION

The hybrid execution model assigns GPU ranks wide beams and otherwise idle CPU ranks narrow beams, combining independent exploration with calibrated load balancing. It also diversifies scoring through multiple lower bounds and achieves high simultaneous CPU and GPU utilization.

  • Machine selection produced monotonic makespan improvement as beam size increased, while computation time grew linearly.
  • Hybrid execution assigns GPU ranks wide beams and idle host ranks narrow CPU beams, with ranks searching independently during the loop.This reclaims otherwise-wasted CPU capacity without inter-rank communication during search.
  • Five scoring modes combine tighter lower bounds for smaller, higher-quality beams with looser bounds for broader search coverage.The bounds are maintained incrementally from machine remaining time, job remaining time, and job readiness variables.
  • Automatic CPU beam-width calibration targets a desired iteration time, adapting CPU work to instance size and hardware without manual tuning.An explicit user-supplied beam width overrides calibration.
  • 94% CPU utilization and 93% GPU utilization were achieved under hybrid execution, compared with 3.1% CPU utilization in GPU-only mode.GPU-only utilization was 98.1%, so the hybrid mode modestly reduced GPU occupancy while using idle host capacity.

VI. EXPERIMENTAL EVALUATION

Across Lawrence benchmarks, the proposed methods progressively improve solution quality through feasible beam construction, parallel diversification, GPU-scale exploration, and hybrid lower-bound scoring. GPU acceleration also improves runtime and multi-GPU scaling.

  • Lawrence benchmark results: G-PMS-BS matches optimal results in 11 of 15 optimally solvable Lawrence instances, while the remaining gaps are at most 1.36%.These are pure construction heuristics without an improvement phase.
  • Lawrence benchmark results: G-PMS-BS and H-PMS-BS achieve new best-known results across the remaining 23 Lawrence instances, including 8% and 7% reductions on LA31 and LA33.The comparison is against PTS on the 30×10 subset.
  • Method progression: G-PMS-BS evaluates thousands of candidates concurrently, supports beam widths up to 25,600, and reduces pruning of promising partial schedules on difficult instances.This broader exploration improves solution quality particularly on large instances.
  • Method progression: H-PMS-BS produces the best overall makespans by combining GPU exploration with lower bounds for more informed beam ranking and pruning.The hybrid approach explores more candidates while ranking them using estimated remaining scheduling cost.
  • GPU performance: Increasing GPUs from 4 to 16 improves Lawrence makespans by 0.3% to 1.4% within the same 10-minute wall-clock limit.The strongest improvements occur on LA32 and LA33.
  • GPU performance: 34.4× speedup is achieved on LA33 and 44.0× on ta80, with the larger instance reaching 88% of the Amdahl ceiling.LA33 execution falls from 4.1 hours to 7.1 minutes and reaches 69% of its 49.9× ceiling.

A. TAILLARD BENCHMARK RESULTS

On the 80 Taillard blocking benchmarks, G-PMS-BS generally outperforms the state-of-the-art Tabu Search, with larger advantages as instance size increases. The strongest gains occur on the largest 100×20 problems.

  • Taillard benchmark results: G-PMS-BS achieves better makespans on 77 of 80 Taillard instances, matches ta24, and is worse only on ta11 and ta13.The two inferior results differ by 8 and 1 makespan units, respectively.
  • Taillard benchmark results: Average makespan reductions reach 5.5% on 50×15 instances and 5.9% on 50×20 instances.The comparison is against Mogali’s tuned Tabu Search baseline.
  • Taillard benchmark results: 10–13% makespan reductions are achieved on the largest 100×20 Taillard instances containing 2,000 operations.ta71 improves by 13.1%, while ta77 improves by 12.8% over the previous state of the art.

VII. CONCLUSION

The paper presents a progression from feasible single-core beam construction to diversified CPU search and massively parallel GPU execution for BJSSP. Across Lawrence and Taillard benchmarks, the GPU approaches obtain strong benchmark results and substantial speedup.

  • Conclusion: The three heuristics progressively scale from single-core construction to CPU-parallel and GPU-parallel execution while retaining K-best feasible partial schedules.The two-phase GPU kernel reduces memory use from gigabytes to megabytes and supports 2,000-operation instances.
  • Conclusion: GPU approaches set new best-known results on 18 of 20 large Lawrence instances and improve 77 of 80 Taillard instances, with reductions up to 13% on 100×20 problems.They also deliver a 44× GPU speedup.
  • Future work: Future work includes adapting the proposed methods to classical JSSP and Flexible JSSP.
Loading 2609.16007v1…