A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems

This paper presents a new, carefully designed algorithm for five bi-objective permutation flow shop scheduling problems that arise from the pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) both, the weighted and non-weighted total tardiness of all jobs. The proposed algorithm combines two search methods, two-phase local search and Pareto local search, which are representative of two different, but complementary, paradigms for multi-objective optimization in terms of Pareto-optimality. The design of the hybrid algorithm is based on a careful experimental analysis of crucial algorithmic components of these two search methods. We compared our algorithm to the two best algorithms identified, among a set of 23 candidate algorithms, in a recent review of the bi-objective permutation flow-shop scheduling problem. We have reimplemented carefully these two algorithms in order to assess the quality of our algorithm. The experimental comparison in this paper shows that the proposed algorithm obtains results that often dominate the output of the two best algorithms from the literature. Therefore, our analysis shows without ambiguity that the proposed algorithm is a new state-of-the-art algorithm for the bi-objective permutation flow-shop problems studied in this paper.     

A high performing metaheuristic for multi-objective flowshop scheduling problem

Genetic algorithm is a powerful procedure for finding an optimal or near optimal solution for the flowshop scheduling problem. This is a simple and efficient algorithm which is used for both single and multi-objective problems. It can easily be utilized for real life applications. The proposed algorithm makes use of the principle of Pareto solutions. It mines the Pareto archive to extract the most repetitive sequences, and constitutes artificial chromosome for generation of the next population. In order to guide the search direction, this approach coupled with variable neighborhood search. This algorithm is applied on the flowshop scheduling problem for minimizing makespan and total weighted tardiness. For the assessment of the algorithm, its performance is compared with the MOGLS [1]. The results of the experiments allow us to claim that the proposed algorithm has a considerable performance in this problem.     

Some single-machine and flowshop scheduling problems with a non-linear deterioration function

The deteriorating job scheduling problems have received increasing attention recently. However, most researchers assume that the actual job processing time is a linear function of its starting time. In fact, in some situations, the deterioration rate might increase or decrease as time passes. For example, the temperature of the ingot in the rolling machine might drop at a slower pace as the surface cools down. Thus, the drop of the ingot temperature might have a decreasing rate. On the other hand, the time to control a fire might go dramatically as time passes, and the time to cease a fire might have an increasing rate. In this paper, we propose a new deteriorating model where the deterioration rate might be increasing or decreasing as time passes. Under the proposed model, we provide the optimal solutions for some single-machine problems and some flowshop problems.     

Some single-machine and m-machine flowshop scheduling problems with learning considerations

Scheduling with learning effect has drawn many researchers’ attention since Biskup [D. Biskup, Single-machine scheduling with learning considerations, European Journal of Opterational Research 115 (1999) 173-178] introduced the concept of learning into the scheduling field. Biskup [D. Biskup, A state-of-the-art review on scheduling with learning effect, European Journal of Opterational Research 188 (2008) 315-329] classified the learning approaches in the literature into two main streams. He claimed that the position-based learning seems to be a realistic model for machine learning, while the sum-of-processing-time-based learning is a model for human learning. In some realistic situations, both the machine and human learning might exist simultaneously. For example, robots with neural networks are used in computers, motor vehicles, and many assembly lines. The actions of a robot are constantly modified through self-learning in processing the jobs. On the other hand, the operators in the control center learn how to give the commands efficiently through working experience. In this paper, we propose a new learning model that unifies the two main approaches. We show that some single-machine problems and some specified flowshop problems are polynomially solvable.     

Decision support for multi-objective flow shop scheduling by the Pareto Iterated Local Search methodology

The article describes the proposition and application of a local search metaheuristic for multi-objective optimization problems. It is based on two main principles of heuristic search, intensification through variable neighborhoods, and diversification through perturbations and successive iterations in favorable regions of the search space. The concept is successfully tested on permutation flow shop scheduling problems under multiple objectives and compared to other local search approaches. While the obtained results are encouraging in terms of their quality, another positive attribute of the approach is its simplicity as it does require the setting of only very few parameters.The metaheuristic is a key element of the Multi-Objective Optimization and Production Planning Solver MOOPPS. The software has been awarded the European Academic Software Award in Ronneby, Sweden (http://www.bth.se/llab/easa_2002.nsf), and has since been used for research and higher education in the mentioned problem domain (Geiger, 2006).     

Note on “Single-machine and flowshop scheduling with a general learning effect model” and “Some single-machine and m-machine flowshop scheduling problems with learning considerations”

In this note, we show that the main results in the two papers [C.C. Wu, W.C. Lee, Single-machine and flowshop scheduling with a general learning effect model, Computers and Industrial Engineering 56 (2009) 1553-1558, W.C. Lee, C.C. Wu, Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information Sciences 179 (2009) 3885-3892] are incorrect.     

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.     

Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect

In this paper, we analyze the two-machine flowshop problem with the makespan minimization and the learning effect, which computational complexity was not determined yet. First, we show that an optimal solution of this problem does not have to be the ‘permutation’ schedule if the learning effect is taken into consideration. Furthermore, it is proved that the permutation and non-permutation versions of this problem are NP-hard even if the learning effect, in a form of a step learning curve, characterizes only one machine. However, if both machines have learning ability and the learning curves are stepwise then the permutation version of this problem is strongly NP-hard. Furthermore, we prove the makespan minimization problem in m-machine permutation proportional flowshop environment remains polynomially solvable with identical job processing times on each machine even if they are described by arbitrary functions (learning curves) dependent on a job position in a sequence. Finally, approximation algorithms for the general problem are proposed and analyzed.     

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.     

On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem

The most efficient approximate procedures so far for the flowshop scheduling problem with makespan objective – i.e. the NEH heuristic and the iterated greedy algorithm – are based on constructing a sequence by iteratively inserting, one by one, the non-scheduled jobs into all positions of an existing subsequence, and then, among the so obtained subsequences, selecting the one yielding the lowest (partial) makespan. This procedure usually causes a high number of ties (different subsequences with the same best partial makespan) that must be broken via a tie-breaking mechanism. The particular tie-breaking mechanism employed is known to have a great influence in the performance of the NEH, therefore different procedures have been proposed in the literature. However, to the best of our knowledge, no tie-breaking mechanism has been proposed for the iterated greedy. In our paper, we present a new tie-breaking mechanism based on an estimation of the idle times of the different subsequences in order to pick the one with the lowest value of the estimation. The computational experiments carried out show that this mechanism outperforms the existing ones both for the NEH and the iterated greedy for different CPU times. Furthermore, embedding the proposed tie-breaking mechanism into the iterated greedy provides the most efficient heuristic for the problem so far.     

求解置换流水车间调度问题的混合鸟群算法

针对置换流水车间调度问题（PFSP）,提出了一种混合鸟群算法（HBSA）以更加有效地最小化最大完工时间。首先,为了改善初始种群的质量和多样性,结合一种基于NEH（Nawaz-Enscore-Ham）的启发式算法和混沌映射提出了一种新的种群初始化方法;其次,为了使算法能够处理离散的调度问题,采用最大排序值（LRV）规则将连续的位置值转换为离散的工件排序;最后,为了强化算法对解空间的探索能力,借鉴变邻域搜索（VNS）和迭代贪婪（IG）算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试,并与目前有效的元启发式算法——刘等提出的混合差分进化算法（L-HDE）、混合共生生物搜索算法（HSOS）、离散狼群算法（DWPA）、多班级教学优化算法（MCTLBO）相比较,结果表明,HBSA取得的最佳相对误差（BRE）、平均相对误差（ARE）的平均值比上述四种算法至少下降了73.3%、76.8%,从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27,仅HBSA的求解结果达到了目前已知最优解,进一步证明了其优越性。     

Single-machine and flowshop scheduling with a general learning effect model

Learning effects in scheduling problems have received growing attention recently. Biskup [Biskup, D. (2008). A state-of-the-art review on scheduling with learning effect. European Journal of Operational Research, 188, 315–329] classified the learning effect scheduling models into two diverse approaches. The position-based learning model seems to be a realistic assumption for the case that the actual processing of the job is mainly machine driven, while the sum-of-processing-time-based learning model takes into account the experience the workers gain from producing the jobs. In this paper, we propose a learning model which considers both the machine and human learning effects simultaneously. We first show that the position-based learning and the sum-of-processing-time-based learning models in the literature are special cases of the proposed model. Moreover, we present the solution procedures for some single-machine and some flowshop problems.     

A multi-objective co-evolutionary algorithm for energy-efficient scheduling on a green data center

Nowadays, the environment protection and the energy crisis prompt more computing centers and data centers to use the green renewable energy in their power supply. To improve the efficiency of the renewable energy utilization and the task implementation, the computational tasks of data center should match the renewable energy supply. This paper considers a multi-objective energy-efficient task scheduling problem on a green data center partially powered by the renewable energy, where the computing nodes of the data center are DVFS-enabled. An enhanced multi-objective co-evolutionary algorithm, called OL-PICEA-g, is proposed for solving the problem, where the PICEA-g algorithm with the generalized opposition based learning is applied to search the suitable computing node, supply voltage and clock frequency for the task computation, and the smart time scheduling strategy is employed to determine the start and finish time of the task on the chosen node. In the experiments, the proposed OL-PICEA-g algorithm is compared with the PICEA-g algorithm, the smart time scheduling strategy is compared with two other scheduling strategies, i.e., Green-Oriented Scheduling Strategy and Time-Oriented Scheduling Strategy, different parameters are also tested on the randomly generated instances. Experimental results confirm the superiority and effectiveness of the proposed algorithm.     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.     

Two-machine flowshop scheduling with flexible operations and controllable processing times

We consider a two-machine flowshop scheduling problem with identical jobs. Each of these jobs has three operations, where the first operation must be performed on the first machine, the second operation must be performed on the second machine, and the third operation (named as flexible operation) can be performed on either machine but cannot be preempted. Highly flexible CNC machines are capable of performing different operations. Furthermore, the processing times on these machines can be changed easily in albeit of higher manufacturing cost by adjusting the machining parameters like the speed and/or feed rate of the machine. The overall problem is to determine the assignment of the flexible operations to the machines and processing times for each operation to minimize the total manufacturing cost and makespan simultaneously. For such a bicriteria problem, there is no unique optimum but a set of nondominated solutions. Using ?-constraint$?\mathrm{-}\mathrm{constraint}$ approach, the problem could be transformed to be minimizing total manufacturing cost for a given upper limit on the makespan. The resulting single criterion problem can be reformulated as a mixed integer nonlinear problem with a set of linear constraints. We use this formulation to optimally solve small instances of the problem while a heuristic procedure is constructed to solve larger instances in a reasonable time.     

Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named “learning effect” has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.     

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

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

Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion

Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems

Storage or buffer capacities between successive machines in flowshop problems may be unlimited, limited or null. The last two cases can lead to blocking situations. In flowshop scheduling literature, many studies have been performed about classical flowshop problems and also about some problems with only one blocking situation between all machines.