A Hybrid Imperialist Competitive Algorithm for the Flexible Job Shop Problem

Xiaodong Lin, Behrooz Ghasemishabankareh, Nasser Shahsavari-Pour, Mohammad-Ali Basiri, Xiaodong LiAcalci 2016 · DOI

TL;DR

This paper introduces HICASA, a novel hybrid algorithm combining Imperialist Competitive Algorithm (ICA) for global search and Simulated Annealing (SA) for local search, to tackle the complex Flexible Job Shop Scheduling Problem (FJSP). HICASA demonstrates superior performance compared to standard Genetic Algorithms (GA) and ICA alone, effectively minimizing the makespan for FJSP instances.

What Problem Does This Paper Address?

The Flexible Job Shop Scheduling Problem (FJSP) is a notoriously difficult combinatorial optimization problem. Unlike the classical Job Shop Scheduling Problem (CJSP), FJSP allows operations to be processed on multiple machines, adding significant flexibility but also complexity. This flexibility is crucial for modern manufacturing to adapt to dynamic demands. However, the increased complexity makes exact methods computationally infeasible. Researchers have turned to meta-heuristic algorithms to find near-optimal solutions efficiently. While various meta-heuristics like GA and SA have been applied, this paper aims to improve upon existing methods by proposing a novel hybrid approach that leverages the strengths of both ICA and SA.

Methods

The core of this paper is the proposed Hybrid Imperialist Competitive Algorithm with Simulated Annealing (HICASA). This algorithm integrates two meta-heuristics:

  • Imperialist Competitive Algorithm (ICA): Used for global exploration of the search space. ICA models a socio-political process where "empires" (consisting of an imperialist and its colonies) compete. The strongest imperialists tend to acquire colonies from weaker ones, driving the search towards better solutions.
  • Simulated Annealing (SA): Employed for local search and fine-tuning. SA is a probabilistic technique that explores the solution space by accepting not only better solutions but also, with a certain probability, worse solutions. This helps escape local optima and refine solutions found by ICA.

HICASA works by using ICA to establish initial empires and then applying SA to selected colonies within each empire to improve them. The algorithm also incorporates a robust parameter design using the Taguchi method to systematically determine optimal parameter settings for HICASA, GA, and ICA, ensuring a fair comparison.

Datasets

The paper evaluates the proposed HICASA algorithm on a specific FJSP instance: a 4 jobs and 5 machines problem. The processing times for this instance are extracted from a previous study ([26]) and presented in Table 1. No new datasets were introduced.

Key Insights and Ideas

  • Synergy of Global and Local Search: The paper highlights the effectiveness of combining a global search algorithm (ICA) with a local search algorithm (SA). This hybrid approach allows for broad exploration of the solution space while also fine-tuning promising solutions, leading to better overall performance.
  • ICA's Potential for FJSP: The research demonstrates that ICA, a relatively newer meta-heuristic, shows promise for solving complex scheduling problems like FJSP.
  • Importance of Parameter Tuning: The use of the Taguchi method underscores the critical role of robust parameter optimization in achieving the best performance from meta-heuristic algorithms. Different algorithms require different parameter configurations to excel.
  • HICASA's Superiority: The experimental results strongly suggest that HICASA outperforms both GA and ICA in terms of solution quality (makespan minimization) for the tested FJSP instance.

Key Results

  • HICASA consistently converged to the optimal makespan value of 11 for the 4x5 FJSP problem in 50 runs.
  • In contrast, GA and ICA did not converge to the optimal makespan in most of their runs, indicating lower solution quality.
  • The Taguchi method identified optimal parameter levels for GA, ICA, and HICASA, which were then used for experimental comparison. For HICASA, the optimal levels were found to be {A2, B2, C1, D3}.

Limitations and Future Work

  • Single Benchmark Instance: The evaluation was performed on a single FJSP instance (4 jobs, 5 machines). While the results are promising, testing on a wider range of benchmark instances with varying sizes and complexities would provide a more comprehensive validation of HICASA's effectiveness.
  • Single Objective: The study focused on minimizing makespan as a single objective. Future work could explore multi-objective FJSP, considering other criteria like total completion time, tardiness, or machine utilization.
  • Integration with Other Meta-heuristics: The authors suggest that HICASA could be integrated with other meta-heuristic algorithms, which could lead to further performance improvements.
  • Application to Other Scheduling Problems: The paper posits that HICASA's applicability extends beyond FJSP to other scheduling problems, which warrants further investigation.

Summary updated

BibTeX
@inproceedings{lin2016hybrid,
  author = {Xiaodong Lin and Behrooz Ghasemishabankareh and Nasser Shahsavari-Pour and Mohammad-Ali Basiri and Xiaodong Li},
  title = {{A Hybrid Imperialist Competitive Algorithm for the Flexible Job Shop Problem}},
  booktitle = {Acalci},
  year = {2016},
  doi = {10.1007/978-3-319-28270-1\_19},
}
Figure