Multicriteria scheduling of two-subassembly products with batch availability and precedence constraints

Zheng Wen, Shuguang LiPeerJ 2025 · DOI

TL;DR

This paper tackles the complex challenge of scheduling products with two subassemblies on a single fabrication line, considering batch processing for common parts and individual processing for unique parts. The authors introduce novel polynomial-time algorithms to optimize both makespan and cost simultaneously, as well as to prioritize multiple objectives lexicographically, under strict or weak precedence constraints. This work offers a computationally efficient way to achieve optimal scheduling for intricate manufacturing scenarios.

What Problem Does This Paper Address?

Modern manufacturing often involves producing complex items that are assembled from multiple components. This paper focuses on a specific scenario: products made of two subassemblies. One is a "common subassembly" shared across all products, which must be processed in batches, incurring a setup time for each batch. The other is a "unique subassembly," specific to each product, processed individually. A key challenge is "batch availability," meaning a common subassembly isn't ready until its entire batch is finished. Furthermore, "precedence constraints" dictate that some products must be completed before others can start.

The core problem is to find the best way to schedule these products on a single machine to achieve multiple, often conflicting, goals. Specifically, the authors address:

  1. Pareto Optimization: Simultaneously minimizing two objectives: the overall completion time (makespan, $C_{max}$) and the maximum cost incurred by any product ($f_{max}$). This is considered under both strict (product B can only start after product A is fully completed) and weak (product B cannot start earlier than product A) precedence constraints.
  2. Lexicographical Optimization: Prioritizing three objectives in a specific order: maximum cost ($f_{max}$), then another maximum cost ($g_{max}$), and finally the makespan ($C_{max}$). This is also handled for both strict and weak precedence constraints.

Existing research often focuses on simpler scenarios or uses heuristics for complex ones. This paper aims to provide exact, computationally efficient solutions for these specific, yet industrially relevant, scheduling problems.

Methods

The paper introduces two main algorithmic approaches, both building upon established scheduling theory:

  • Algorithm $C_{max}$-$F_{max}$ (for Pareto Optimization): This algorithm adapts Lawler's algorithm for minimizing maximum cost under precedence constraints. It works by scheduling products in reverse order, iteratively adjusting the schedule to satisfy both precedence and the dual objectives. The key innovation lies in how it handles the batch availability of common subassemblies and the individual processing of unique subassemblies within the framework of Pareto optimality. It achieves an $O(n^4)$ time complexity for strict precedence and $O(n)$ for weak precedence.
  • Algorithm $F_{max}$-$G_{max}$-$C_{max}$ (for Lexicographical Optimization): This algorithm builds upon the $C_{max}$-$F_{max}$ approach. It first uses the $C_{max}$-$F_{max}$ algorithm to find an optimal schedule for the primary objective ($f_{max}$) and then iteratively refines it to optimize the secondary objective ($g_{max}$) while maintaining optimality for the primary one. Finally, it optimizes the makespan ($C_{max}$) as the tertiary objective. This is also achieved with $O(n^4)$ time complexity for strict precedence and $O(n)$ for weak precedence.

A crucial aspect of both algorithms is their ability to handle the batch processing of common subassemblies and the individual processing of unique subassemblies, while respecting precedence constraints. They leverage concepts like product-subsequences and carefully manage the timing of batch completions and individual task starts.

Datasets

The paper does not explicitly mention using pre-existing datasets. Instead, it describes experiments conducted on randomly generated instances to evaluate the performance of the proposed algorithms. The parameters varied include the number of jobs ($n$), processing times for common subassemblies (uniformly distributed integer range [1, 5]), and processing times for unique subassemblies (uniformly distributed integer range [1, 10]).

Key Insights and Ideas

  • Bridging Theory and Practice: The paper demonstrates that complex, multi-objective scheduling problems with batching and precedence constraints, common in real-world manufacturing, can be solved optimally using polynomial-time algorithms. This is a significant step beyond relying solely on heuristics for such problems.
  • The Power of Reverse Scheduling: Adapting Lawler's reverse-order scheduling approach proves effective for optimizing makespan and cost under precedence constraints, even with the added complexity of batch availability.
  • Hierarchical Optimization for Multiple Goals: The lexicographical optimization approach provides a structured way to handle multiple, prioritized objectives, offering a more nuanced solution than simple Pareto optimization when clear priorities exist.
  • Precedence Constraints Significantly Impact Performance: The experimental results highlight that precedence constraints, while adding complexity, can actually reduce computational overhead compared to scenarios without them, suggesting a more constrained problem space can be easier to solve optimally.

Key Results

  • $O(n^4)$ Algorithms for Complex Scheduling: The paper presents $O(n^4)$-time algorithms for solving four distinct multicriteria scheduling problems involving two-subassembly products with batch availability and precedence constraints.
  • Efficient Solutions for Pareto Optimization: For the problem of simultaneously minimizing makespan ($C_{max}$) and maximum cost ($f_{max}$) under strict precedence, the algorithm achieves $O(n^4)$ time. For weak precedence, it's even faster at $O(n)$.
  • Efficient Solutions for Lexicographical Optimization: For the problem of lexicographically optimizing $f_{max}$, $g_{max}$, and $C_{max}$ under strict precedence, the algorithm also runs in $O(n^4)$ time. For weak precedence, it's $O(n)$.
  • Experimental Validation: The algorithms were tested on randomly generated instances, showing polynomial scaling of runtime with the number of jobs, consistent with their theoretical complexity. The experiments also demonstrated that the algorithms with precedence constraints were computationally more efficient than those without.

Limitations and Future Work

  • Time Complexity: While $O(n^4)$ is polynomial, it can still be computationally intensive for very large problem instances. The authors suggest exploring algorithms with improved time complexity.
  • Generalizing Objectives: The paper focuses on specific objective functions ($C_{max}$, $f_{max}$, $g_{max}$). Future work could explore Pareto optimization for more general min-max or min-sum objective functions.
  • Industrial Applicability: The authors highlight several promising avenues for extending the research to better match industrial needs:
  • Parallelization: Developing GPU-accelerated or distributed (MapReduce) implementations to handle large-scale industrial instances efficiently.
  • Dynamic Precedence: Extending the model to handle real-time updated precedence graphs, crucial for flexible manufacturing systems and Industry 4.0.
  • Energy-Aware Optimization: Incorporating energy consumption as an additional objective in the lexicographical framework, aligning with sustainability trends.

Summary updated

Abstract

This article studies the multicriteria problems of scheduling a set of n products on a fabrication facility, focusing on batch availability and precedence constraints. Each product is composed of two distinct subassemblies: a common subassembly, shared across all products, and a unique subassembly unique to each product. The common subassemblies are processed together in batches, with each batch requiring an initial setup, while unique subassemblies are handled individually. The availability of a common subassembly is contingent upon the completion of its entire batch (<i>i.e</i>., batch availability), whereas a unique subassembly becomes available immediately after its processing. The product completion time is determined by the availability of both subassemblies. Strict (weak) precedence means that if a product precedes another, then the latter can start only after the former is completed (the latter cannot start earlier than the former). We propose O(n<sup>4</sup>)-time algorithms to simultaneously optimize makespan and maximum cost, as well as to lexicographically optimize two maximum costs and makespan under strict or weak precedence constraints.
BibTeX
@inproceedings{wen2025multicriteria,
  author = {Zheng Wen and Shuguang Li},
  title = {{Multicriteria scheduling of two-subassembly products with batch availability and precedence constraints}},
  booktitle = {PeerJ},
  year = {2025},
  doi = {10.7717/peerj-cs.3093},
}
Figure