Hybrid artificial immune system and extremal optimization algorithm for permutation flowshop scheduling problem

The permutation flowshop scheduling problem （PFSP） is one of the most well-known and well-studied production scheduling problems with strong industrial background. This paper presents a new hybrid optimization algorithm which combines the strong global search ability of artificial immune system （AIS） with a strong local search ability of extremal optimization （EO） algorithm. The proposed algorithm is applied to a set of benchmark problems with a makespan criterion. Performance of the algorithm is evaluated. Comparison results indicate that this new method is an effective and competitive approach to the PFSP.

An Iterated Greedy Algorithm with Memory and Learning Mechanisms for the Distributed Permutation Flow Shop Scheduling Problem

The distributed permutation flow shop scheduling problem(DPFSP)has received increasing attention in recent years.The iterated greedy algorithm(IGA)serves as a powerful optimizer for addressing such a problem because of its straightforward,single-solution evolution framework.However,a potential draw-back of IGA is the lack of utilization of historical information,which could lead to an imbalance between exploration and exploitation,especially in large-scale DPFSPs.As a consequence,this paper develops an IGA with memory and learning mechanisms(MLIGA)to efficiently solve the DPFSP targeted at the mini-malmakespan.InMLIGA,we incorporate a memory mechanism to make a more informed selection of the initial solution at each stage of the search,by extending,reconstructing,and reinforcing the information from previous solutions.In addition,we design a twolayer cooperative reinforcement learning approach to intelligently determine the key parameters of IGA and the operations of the memory mechanism.Meanwhile,to ensure that the experience generated by each perturbation operator is fully learned and to reduce the prior parameters of MLIGA,a probability curve-based acceptance criterion is proposed by combining a cube root function with custom rules.At last,a discrete adaptive learning rate is employed to enhance the stability of the memory and learningmechanisms.Complete ablation experiments are utilized to verify the effectiveness of the memory mechanism,and the results show that this mechanism is capable of improving the performance of IGA to a large extent.Furthermore,through comparative experiments involving MLIGA and five state-of-the-art algorithms on 720 benchmarks,we have discovered that MLI-GA demonstrates significant potential for solving large-scale DPFSPs.This indicates that MLIGA is well-suited for real-world distributed flow shop scheduling.

Multi-objective Optimization of the Distributed Permutation Flow Shop Scheduling Problem with Transportation and Eligibility Constraints

In this paper,we consider the distributed permutation flow shop scheduling problem(DPFSSP)with transportation and eligibility constrains.Three objectives are taken into account,i.e.,makespan,maximum lateness and total costs(transportation costs and setup costs).To the best of our knowledge,there is no published work on multi-objective optimization of the DPFSSP with transportation and eligibility constraints.First,we present the mathematics model and constructive heuristics for single objective;then,we propose an improved The Nondominated Sorting Genetic Algorithm II(NSGA-II)for the multi-objective DPFSSP to find Pareto optimal solutions,in which a novel solution representation,a new population re-/initialization,effective crossover and mutation operators,as well as local search methods are developed.Based on extensive computational and statistical experiments,the proposed algorithm performs better than the well-known NSGA-II and the Strength Pareto Evolutionary Algorithm 2(SPEA2).