Hybrid heuristic algorithm for multi-objective scheduling problem

Peng Jian-gang, Mingzhou Liu, Xi Zhang, Ling LinJournal of Systems Engineering and Electronics 2019 · DOI

TL;DR

This paper introduces a novel hybrid algorithm, OGHS, that combines Harmony Search with Opposition-Based Learning and recursive halving to efficiently solve the complex multi-objective flexible job-shop scheduling problem (MOFJSP). The OGHS algorithm demonstrates superior performance in finding optimal scheduling solutions and selecting the best one for decision-makers, outperforming existing methods on benchmark instances.

What Problem Does This Paper Address?

The flexible job-shop scheduling problem (FJSP) is a real-world challenge in manufacturing where operations can be performed on multiple machines. When multiple, often conflicting, objectives need to be optimized simultaneously (e.g., minimizing makespan, total workload, and critical machine workload), it becomes a multi-objective flexible job-shop scheduling problem (MOFJSP). Solving MOFJSPs is complex because it involves not only finding a set of optimal trade-off solutions (Pareto front) but also selecting the most appropriate solution from this set based on decision-maker preferences. Existing methods struggle to balance exploration and exploitation, maintain diversity in solutions, and efficiently converge to optimal or near-optimal solutions, especially for large-scale problems.

Methods

The core of this paper is the proposed Oppositional Global-Based Harmony Search (OGHS) algorithm. Here's a breakdown of its key components:

  • Harmony Search (HS): A meta-heuristic algorithm inspired by music improvisation. It maintains a "harmony memory" (HM) of good solutions and iteratively improvises new solutions.
  • Opposition-Based Learning (OBL): This technique is used to generate "opposite" solutions to existing ones. By initializing the population with both the original and their opposite points, OBL helps to improve the diversity of initial solutions and accelerate convergence. In OGHS, OBL is specifically applied to the operation sequence part of the harmony vector.
  • Recursive Halving: This method is employed to efficiently shrink the search space. By iteratively halving the search space based on non-dominated solutions, it helps the algorithm converge faster.
  • Dual Vector Code: A novel encoding scheme is used to represent the scheduling problem. This vector consists of two parts: one for the operation sequence and another for machine allocation. This allows the algorithm to handle the discrete nature of the MOFJSP.
  • Pareto Optimality: Used to identify and maintain a set of non-dominated solutions, representing the trade-offs between different objectives.
  • TOPSIS (Technique for Order Preference by Similarity to an Ideal Solution): After generating the set of non-dominated solutions, TOPSIS is used as a multi-attribute decision-making (MADM) tool to select the single most appropriate solution based on predefined criteria (makespan, total workload, critical machine workload).

The OGHS algorithm integrates these components: it uses OBL for better initial population diversity, a global-based HS variant for efficient search, and recursive halving to speed up convergence.

Datasets

The paper evaluates the proposed OGHS algorithm on:

  • Multi-objective test functions: DTLZ1-4 and DTLZ7. These are standard benchmarks used for evaluating multi-objective optimization algorithms, particularly for assessing population diversity and iterative convergence. DTLZ1-4 are continuous, while DTLZ7 is non-continuous.
  • Benchmark instances for MOFJSP:
    • Two "Kacem" instances (medium scale: 10x10, and large scale: 15x10).
  • One "Brandimarte" instance (larger scale: 20x10). These instances are derived from existing literature and represent realistic flexible job-shop scheduling scenarios.

Key Insights and Ideas

  • Synergy of OBL and Recursive Halving: The combination of OBL for initial diversity and recursive halving for focused search significantly enhances the performance of the Harmony Search algorithm for MOFJSP. This dual approach addresses both the exploration and exploitation challenges.
  • Encoding for Discrete Problems: The dual vector code representation is crucial for effectively applying a population-based meta-heuristic like HS to the discrete nature of scheduling problems.
  • Two-Stage Approach is Effective: Separating the problem into finding a diverse set of Pareto optimal solutions and then using a decision-making technique (TOPSIS) to select the best one is a practical and effective strategy for MOFJSP.
  • Importance of Initialization: The paper highlights that simple random initialization is insufficient for complex problems. Integrating OBL into the initialization process dramatically improves the quality and diversity of the initial population.
  • Trade-offs in Performance Metrics: While OGHS might have a slightly higher theoretical time complexity than basic HS, the recursive halving significantly speeds up the actual search process, leading to better overall performance in terms of convergence and solution quality.

Key Results

  • Improved Solution Quality: The OGHS algorithm consistently found non-dominated solutions that were either superior or comparable to those obtained by well-known algorithms (PSO+SA, AIA, MOGA, P-DABC) on the tested MOFJSP benchmarks. In several cases, the OGHS solutions dominated those of other algorithms.
  • Faster Convergence: Convergence curves (Figs. 6-10) show that the OGHS algorithm converges much faster than the basic HS and HS+OBL algorithms, especially in terms of generational distance.
  • Effective Decision Support: The TOPSIS method successfully identified a single, most appropriate scheduling scheme from the generated non-dominated set, demonstrating its utility in practical decision-making.
  • Performance on DTLZ Functions: The OGHS algorithm generally outperformed HS and HS+OBL on the DTLZ test functions, particularly in terms of generational distance (GD) and inverted generational distance (IGD), except for DTLZ2 where HS+OBL was slightly better.

Limitations and Future Work

  • Robustness and Time Efficiency: The authors acknowledge that further improvements in the robustness and time efficiency of the OGHS algorithm are needed.
  • Large-Scale Instances: While the algorithm performed well on larger instances, further investigation into its performance on even larger-scale problems is suggested.
  • Coding Schemes and Strategies: The paper points out that the choice of coding schemes and algorithm strategies significantly impacts efficiency. Future work should thoroughly investigate these aspects.
  • Additional Objectives and Uncertainties: The authors suggest that future research should consider incorporating additional objectives and handling uncertainties within the MOFJSP framework.

Summary updated

BibTeX
@article{jiangang2019hybrid,
  author = {Peng Jian-gang and Mingzhou Liu and Xi Zhang and Ling Lin},
  title = {{Hybrid heuristic algorithm for multi-objective scheduling problem}},
  journal = {Journal of Systems Engineering and Electronics},
  year = {2019},
  doi = {10.21629/jsee.2019.02.12},
}
Figure