Optimization of Iterated Greedy Algorithm for Distributed Blocking Flowshop Group Robust Scheduling Problem

0
0
0

Optimization of Iterated Greedy Algorithm for Distributed Blocking Flowshop Group Robust Scheduling Problem

Introduction

Modern manufacturing environments, particularly in industries like printed circuit board assembly, often involve complex production systems with multiple identical production lines across different locations. These systems can be abstracted as distributed flowshop group scheduling problems (DFGSP), which incorporate sequence-dependent setup times (SDST) between different groups of workpieces. A critical challenge in such systems arises from the absence or insufficiency of buffers between machines, leading to blocking constraints where completed workpieces must remain on their current machine until the next machine becomes available. This creates what is known as the distributed blocking flowshop group scheduling problem (DBFGSP).

Adding to the complexity, real-world production environments face uncertainties in processing times due to factors like machine maintenance, worker skill variations, and environmental changes. These uncertainties mean that solutions based on predetermined processing times may perform poorly under varying conditions. To address this, the multi-scenario approach is employed, where multiple sets of processing times represent different possible scenarios. This leads to the DBFGSP with uncertain processing times (DBFGSP-UPT).

Customer satisfaction is another crucial factor, often reflected in delivery time windows. Early deliveries can cause inventory buildup, while late deliveries reduce customer satisfaction. The total weighted earliness and tardiness (TWET) metric captures these effects, balancing inventory costs against delivery delays. The robust optimization (RO) objective integrates both the mean and standard deviation of TWET across scenarios, ensuring solutions perform well on average while maintaining stability across different conditions.

Given the NP-hard nature of distributed flowshop scheduling problems with TWET objectives, the additional constraints and objectives in DBFGSP-UPT further increase its complexity. Key challenges include:

  1. Modeling Complexity: Existing mathematical models do not account for blocking constraints, delivery time windows, and uncertain processing times.
  2. Idle Time Insertion: Traditional idle time insertion methods, which optimize TWET by delaying processing on the last machine, are incompatible with blocking constraints.
  3. Computational Efficiency: DBFGSP-UPT involves three strongly coupled subproblems—factory assignment, group scheduling, and job sequencing—requiring efficient algorithms to handle the high computational complexity.

To address these challenges, this study makes several contributions:
• A mixed-integer linear programming (MILP) model for DBFGSP-UPT, validated using the Gurobi solver.

• A modified idle time insertion (MITI) method that accommodates blocking and group constraints by inserting idle times across all machines.

• An adaptive cooperative iterated greedy algorithm (ACIG_ITI) that integrates MITI, featuring scenario-aware initialization, adaptive destruction, and accelerated reconstruction and local search strategies.

Problem Description

The DBFGSP-UPT involves scheduling jobs across multiple identical factories, each consisting of a flowshop with m machines. Jobs are grouped into δ groups, with sequence-dependent setup times between groups. Key constraints include:
• Zero Buffers: Blocking occurs when a completed job cannot proceed to the next machine if it is occupied.

• Uncertain Processing Times: Represented through multiple scenarios, each with different processing time realizations.

• Delivery Time Windows: Each group has an earliest and latest delivery time, with penalties for early or late completion.

The objective is to minimize the robust optimization (RO) metric, which balances the average TWET across scenarios with its variability.

Mathematical Model

The MILP model for DBFGSP-UPT includes decision variables for group and job sequencing, completion times, and penalties for earliness and tardiness. Constraints ensure:
• Each group has exactly one predecessor and successor.

• Virtual groups (representing the start and end of sequences) are used to model factory assignments.

• Job sequences within groups are continuous and uninterrupted.

• Blocking constraints prevent jobs from proceeding to occupied machines.

• Delivery time windows enforce penalties for deviations.

The RO objective combines the mean and standard deviation of TWET across scenarios, weighted by a preference coefficient ρ (set to 0.95 to prioritize mean performance over variability).

Algorithm Design

Solution Representation

Solutions are encoded using two vectors:

  1. Group Sequencing: A 2D vector representing the sequence of groups in each factory.
  2. Job Sequencing: A 2D vector representing the sequence of jobs within each group.

Algorithm Framework

ACIG_ITI alternates between group-level and job-level optimization phases, dynamically adjusting focus based on a threshold parameter GJ (set to 0.8). Key components include:

  1. Initialization: Uses a modified NEH heuristic (MNEH2_en) that considers multi-scenario processing times and delivery windows.
  2. Adaptive Destruction: Randomly removes groups or jobs, adjusting the destruction size based on solution improvement.
  3. Reconstruction: Employs greedy insertion with MITI to optimize RO, using an accelerated stepwise search to reduce computational effort.
  4. Local Search: Alternates between group and job-level refinements, leveraging MITI to improve solutions.

Modified Idle Time Insertion (MITI)

MITI addresses blocking constraints by inserting idle times across all machines, not just the last one. Key steps:

  1. Preprocessing: Computes job completion times and identifies minimum intervals for idle time insertion.
  2. Block Identification: Groups are categorized into blocks where idle time cannot be inserted between them.
  3. Idle Time Allocation: Idle times are inserted before blocks to reduce earliness penalties without violating blocking constraints.

Experimental Results

Instance Generation

810 test instances were generated, varying in:
• Factories (f = 2, 3, 4).

• Groups (δ = 20, 40, 60).

• Machines (m = 2, 4, 6).

• Processing time uncertainty (10 scenarios with varying ranges).

• Delivery windows, derived from modified LPT and NEH2 schedules.

Model Validation

The MILP model was validated on small instances using Gurobi, confirming its correctness. However, its performance degraded with problem size, while ACIG_ITI consistently produced high-quality solutions efficiently.

Algorithm Performance

ACIG_ITI was compared against four state-of-the-art metaheuristics (sIGA, sILSA, CIGA, TIGA) enhanced with MITI. Key findings:
• ARO Improvement: ACIG_ITI reduced average RO by 30.48%–37.73% compared to other algorithms.

• ARDI Dominance: ACIG_ITI achieved an ARDI of 0, indicating it consistently found the best solutions.

• Robustness: Performance advantages held across all problem sizes and configurations.

Statistical tests (Friedman and Wilcoxon signed-rank) confirmed the superiority of ACIG_ITI with p-values < 0.05.

Conclusion

This study addressed the DBFGSP-UPT, introducing a robust MILP model and an efficient ACIG_ITI algorithm. Key innovations include the MITI method for blocking constraints and a cooperative optimization framework balancing group and job-level scheduling. Experimental results demonstrated significant improvements over existing methods, highlighting ACIG_ITI’s effectiveness in handling uncertainty and complex constraints.

Future work could explore integrating reinforcement learning to further enhance solution quality for larger or more complex instances.

doi.org/10.19734/j.issn.1001-3695.2024.07.0232

Was this helpful?

0 / 0