Multi-objective colonial competitive algorithm for hybrid flowshop problem

This study analyses the multi-objective optimization in hybrid flowshop problem, in which two conflicting objectives, makespan and total weighted tardiness, are considered to be minimized simultaneously. The multi-objective version of Colonial Competitive Algorithm (CCA) for real world optimization problem is introduced and investigated. In contrast to multi-objective problems solved by CCA, presented in the literature, which used the combination of the objectives as single objective, the proposed algorithm is established on Pareto solutions concepts. Another novelty of this paper is estimating the power of each imperialist by a probabilistic criterion for this multi objective algorithm. Besides that, the variable neighborhood search is implemented as an assimilation strategy. Performance of the algorithm is finally compared with a famous algorithm for scheduling problem, NSGA-II, and the multi-objective form of CCA [28].     

A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA.     

A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution

The hybrid flowshop scheduling problem (HFSP) has been widely studied in the past decades. The most commonly used criterion is production efficiency. Green criteria, such as energy consumption and carbon emission, have attracted growing attention with the improvement of the environment protection awareness. Limited attention has been paid to noise pollution. However, noise pollution can lead to health and emotion disorder. Thus, this paper studies a multi-objective HFSP considering noise pollution in addition to production efficiency and energy consumption. First, we formulate a new mixed-integer programming model for this multi-objective HFSP. To realize the green scheduling, one energy conservation/noise reduction strategy is embedded into this model. Then, a novel multi-objective cellular grey wolf optimizer (MOCGWO) is proposed to address this problem. The proposed MOCGWO integrates the merits of cellular automata (CA) for diversification and variable neighborhood search (VNS) for intensification, which balances exploration and exploitation. Finally, to validate the efficiency and effectiveness of the proposed MOCGWO, we compare our proposal with other well-known multi-objective evolutionary algorithms by conducting comparison experiments. The experimental results show that the proposed MOCGWO is significantly better than its competitors on this problem.     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems

Multi-objective optimisation problems have seen a large impulse in the last decades. Many new techniques for solving distinct variants of multi-objective problems have been proposed. Production scheduling, as with other operations management fields, is no different. The flowshop problem is among the most widely studied scheduling settings. Recently, the Iterated Greedy methodology for solving the single-objective version of the flowshop problem has produced state-of-the-art results. This paper proposes a new algorithm based on Iterated Greedy technique for solving the multi-objective permutation flowshop problem. This algorithm is characterised by an effective initialisation of the population, management of the Pareto front, and a specially tailored local search, among other things. The proposed multi-objective Iterated Greedy method is shown to outperform other recent approaches in comprehensive computational and statistical tests that comprise a large number of instances with objectives involving makespan, tardiness and flowtime. Lastly, we use a novel graphical tool to compare the performances of stochastic Pareto fronts based on Empirical Attainment Functions.     

An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed

This paper deals with the scheduling problem of minimizing the makespan in a permutational flowshop environment with the possibility of outsourcing certain jobs. It addresses this problem by means of the development of an ant colony optimization-based algorithm. This new algorithm, here named as flowshop ant colony optimization is composed of two combined ACO heuristics. The results show that this new approach can be used to solve the problem efficiently and in a short computational time.     

Ensemble of multi-objective metaheuristic algorithms for multi-objective unconstrained binary quadratic programming problem

Metaheuristics have been widely utilized for solving NP-hard optimization problems. However, these algorithms usually perform differently from one problem to another, i.e., one may be effective on a problem but performs badly on another problem. Therefore, it is difficult to choose the best algorithm in advance for a given problem. In contrast to selecting the best algorithm for a problem, selection hyper-heuristics aim at performing well on a set of problems (instances). This paper proposes a selection hyper-heuristic based algorithm for multi-objective optimization problems. In the proposed algorithm, multiple metaheuristics exhibiting different search behaviors are managed and controlled as low-level metaheuristics in an algorithm pool, and the most appropriate metaheuristic is selected by means of a performance indicator at each search stage. To assess the performance of the proposed algorithm, an implementation of the algorithm containing four metaheuristics is proposed and tested for solving multi-objective unconstrained binary quadratic programming problem. Experimental results on 50 benchmark instances show that the proposed algorithm can provide better overall performance than single metaheuristics, which demonstrates the effectiveness of the proposed algorithm.     

Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem

Finding a Pareto-optimal frontier is widely favorable among researchers to model existing conflict objectives in an optimization problem. Project scheduling is a well-known problem in which investigating a combination of goals eventuate in a more real situation. Although there are many different types of objectives based on the situation on hand, three basic objectives are the most common in the literature of the project scheduling problem. These objectives are: (i) the minimization of the makespan, (ii) the minimization of the total cost associated with the resources, and (iii) the minimization of the variability in resources usage. In this paper, three genetic-based algorithms are proposed for approximating the Pareto-optimal frontier in project scheduling problem where the above three objectives are simultaneously considered. For the above problem, three self-adaptive genetic algorithms, namely (i) A two-stage multi-population genetic algorithm (MPGA), (ii) a two-phase subpopulation genetic algorithm (TPSPGA), and (iii) a non-dominated ranked genetic algorithm (NRGA) are developed. The algorithms are tested using a set of instances built from benchmark instances existing in the literature. The performances of the algorithms are evaluated using five performance metrics proposed in the literature. Finally according to the technique for order preference by similarity to ideal solution (TOPSIS) the self-adaptive NRGA gained the highest preference rank, followed by the self-adaptive TPSPGA and MPGA, respectively.     

A multi-objective evolutionary approach for generator scheduling

This paper presents a novel, two-phase approach for optimal generation scheduling, taking into account the environmental issue of emission allowance trading in addition to the economic issue of operation cost. In the first phase, hourly-optimal scheduling is done to simultaneously minimize operation cost, emission, and transmission loss, while satisfying constraints such as power balance, spinning reserve and power generation limits. In the second phase, the minimum up/down time and ramp up/down rate constraints are considered, and a set of 24-h optimal schedules is obtained using the outputs of the first phase. Simulation results indicate effectiveness of the proposed approach.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

.求解小批量流水线调度问题的混合微粒群算法*

针对基于交货期的小批量流水线调度问题,提出了一种微粒群优化算法。其中利用最小位置值(smallest position value,SPV)规则,使具有连续本质的微粒群算法能直接应用于调度问题,并通过动态调整参数平衡算法的全局搜索和局部搜索的能力。针对微粒群算法容易陷入局部最优的缺陷,利用模拟退火算法的概率突跳机制改进其优化性能,并设计了三种微粒群模拟退火混合算法。最后,仿真实验表明所得算法具有良好的寻优特性与运算效率。     

蛙跳优化算法求解多目标无等待流水线调度

提出了基于Pareto边界和档案集的改进蛙跳算法,解决以最大完工时间、最大拖后时间和总流经时间为目标值的无等待流水线调度问题．首先,采用NEH（Nawaz—Enscore—Ham）启发式与随机解相结合的初始化方法,保证了初始群体的质量和分布性;其次,采用两点交叉方法生成新解,使蛙跳算法能够直接用于解决调度问题;再次,利用非支配解集动态更新群体,改善了群体的质量和多样性;最后,将基于插入邻域的快速局部搜索算法嵌入到蛙跳算法中,增强了算法的开发能力和效率．仿真试验表明了所得蛙跳算法的有效性和高效性．     

An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.     

A robust scheduling method based on a multi-objective immune algorithm

A robust scheduling method is proposed to solve uncertain scheduling problems. An uncertain scheduling problem is modeled by a set of workflow models, and then a scheduling scheme (solution) of the problem can be evaluated by workflow simulations executed with the workflow models in the set. A multi-objective immune algorithm is presented to find Pareto optimal robust scheduling schemes that have good performance for each model in the set. The two optimization objectives for scheduling schemes are the indices of the optimality and robustness of the scheduling results. An antibody represents a resource allocation scheme, and the methods of antibody coding and decoding are designed to deal with resource conflicts during workflow simulations. Experimental tests show that the proposed method can generate a robust scheduling scheme that is insensitive to uncertain scheduling environments.     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.     

A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem

The genetic algorithm with search area adaptation (GSA) has a capacity for adapting to the structure of solution space and controlling the tradeoff balance between global and local searches, even if we do not adjust the parameters of the genetic algorithm (GA), such as crossover and/or mutation rates. But, GSA needs the crossover operator that has ability for characteristic inheritance ratio control. In this paper, we propose the modified genetic algorithm with search area adaptation (mGSA) for solving the Job-shop scheduling problem (JSP). Unlike GSA, our proposed method does not need such a crossover operator. To show the effectiveness of the proposed method, we conduct numerical experiments by using two benchmark problems. It is shown that this method has better performance than existing GAs.     

Hybrid sliding level Taguchi-based particle swarm optimization for flowshop scheduling problems

A hybrid sliding level Taguchi-based particle swarm optimization (HSLTPSO) algorithm is proposed for solving multi-objective flowshop scheduling problems (FSPs). The proposed HSLTPSO integrates particle swarm optimization, sliding level Taguchi-based crossover, and elitist preservation strategy. The novel contribution of the proposed HSLTPSO is the use of a PSO to explore the optimal feasible region in macro-space, the use of a systematic reasoning mechanism of the sliding level Taguchi-based crossover to exploit the better solution in micro-space, and the use of the elitist preservation strategy to retain the best particles of multi-objective population for next iteration. The sliding level Taguchi-based crossover is embedded in the PSO to find the best solutions and consequently enhance the PSO. Using the systematic reasoning way of the Taguchi-based crossover with considering the influence of tuning factors α, β and γ is presented in this study to solve the conflicting problem of non-feasible solutions and to find the better particles. As a result, it exhibits a significant improvement in Pareto best solutions of the FSP. By combining the advantages of exploration and exploitation, from the computational experiments of the six test problems, the HSLTPSO provides better results compared to the existing methods reported in the literature when solving multi-objective FSPs. Therefore, the HSLTPSO is an effective approach in solving multi-objective FSPs.     

New simple constructive heuristic algorithms for minimizing total flow-time in the permutation flowshop scheduling problem

This paper develops a set of new simple constructive heuristic algorithms to minimize total flow-time for an $n$-jobs×$m$-machines permutation flowshop scheduling problem. We first propose a new iterative algorithm based on the best existing simple heuristic algorithm, and then integrate new indicator variables for weighting jobs into this algorithm. We also propose new decision criteria to select the best partial sequence in each iteration of our algorithm. A comprehensive numerical experiment reveals that our modifications and extensions improve the effectiveness of the best existing simple heuristic without affecting its computational efficiency.     

资源受限项目调度问题的改进类电磁算法

在资源受限项目调度中,工序必须在特定时间窗口中执行。为此,在类电磁(EM)算法的基础上提出一种基于变邻域搜索(VNS)的改进类电磁算法(IEMA)。采用VNS作为IEMA的局部搜索策略,对EM算法中的电荷、合力以及粒子解移动的方式做改进。将IEMA应用于求解标准问题库PSPLIB,并与EM、IEM以及基于邻域搜索的改进类电磁算法IEM-NS进行比较分析,仿真结果表明,IEMA具有更好的求解性能。     

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on m machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard’s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling problems.