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.     

A Self-guided Genetic Algorithm for permutation flowshop scheduling problems

In this paper we develop a Self-guided Genetic Algorithm (Self-guided GA), which belongs to the category of Estimation of Distribution Algorithms (EDAs). Most EDAs explicitly use the probabilistic model to sample new solutions without using traditional genetic operators. EDAs make good use of the global statistical information collected from previous searches but they do not efficiently use the location information about individual solutions. It is recently realized that global statistical information and location information should complement each other during the evolution process. In view of this, we design the Self-guided GA based on a novel strategy to combine these two kinds of information. The Self-guided GA does not sample new solutions from the probabilistic model. Instead, it estimates the quality of a candidate offspring based on the probabilistic model used in its crossover and mutation operations. In such a way, the mutation and crossover operations are able to generate fitter solutions, thus improving the performance of the algorithm. We tested the proposed algorithm by applying it to deal with the NP-complete flowshop scheduling problem to minimize the makespan. The experimental results show that the Self-guided GA is very promising. We also demonstrate that the Self-guided GA can be easily extended to treat other intractable combinatorial problems.     

A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem

In this paper, a discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of Taillard [Benchmarks for basic scheduling problems. European Journal of Operational Research 1993;64:278–85] by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by Carlier [Ordonnancements a contraintes disjonctives. RAIRO Recherche operationelle 1978;12:333–51], Heller [Some numerical experiments for an M×J$\mathrm{M}\times \mathrm{J}$ flow shop and its decision-theoretical aspects. Operations Research 1960;8:178–84], and Revees [A genetic algorithm for flowshop sequencing. Computers and Operations Research 1995;22:5–13] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by Rajendran [A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 1994;45:472–8] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14] were improved by the VND version of the DPSO algorithm.     

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.     

An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems

In this work we propose an estimation of distribution algorithm (EDA) as a new tool aiming at minimizing the total flowtime in permutation flowshop scheduling problems. A variable neighbourhood search is added to the algorithm as an improvement procedure after creating a new offspring. The experiments show that our approach outperforms all existing techniques employed for the problem and can provide new upper bounds.     

Makespan distribution of permutation flowshop schedules

The makespan distribution of permutation flowshop schedules has been a topic of debate for almost fifty years. Many researchers have confirmed or doubted the famous claim that the makespan distribution of permutation flowshop schedules is asymptotically normal if the number of jobs is sufficiently large. This paper theoretically and empirically investigates the makespan distribution of permutation flowshop schedules and shows that the normality claim is not valid for the job-dominated and machine-dominated flowshops. Errors in the proof of normality of the makespan distribution of permutation flowshop schedules are pointed out. It is shown that the makespan distribution of a permutation flowshop scheduling problem depends on the number of jobs as well as the number of machines.     

A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan

A common assumption in the classical permutation flowshop scheduling model is that each job is processed on each machine at most once. However, this assumption does not hold for a re-entrant flowshop in which a job may be operated by one or more machines many times. Given that the re-entrant permutation flowshop scheduling problem to minimize the makespan is very complex, we adopt the CPLEX solver and develop a memetic algorithm (MA) to tackle the problem. We conduct computational experiments to test the effectiveness of the proposed algorithm and compare it with two existing heuristics. The results show that CPLEX can solve mid-size problem instances in a reasonable computing time, and the proposed MA is effective in treating the problem and outperforms the two existing heuristics.     

Polynomial time algorithms for the UET permutation flowshop problem with time delays

This paper addresses the problem of scheduling a set of n unit execution time (UET) jobs on an m-permutation flowshop with arbitrary time delays, so as to minimize the makespan criterion. A polynomial time algorithm is exhibited for the three-machine and four-machine cases, respectively.     

A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem

This paper presents a variable iterated greedy algorithm (IG) with differential evolution (vIG_DE), designed to solve the no-idle permutation flowshop scheduling problem. In an IG algorithm, size d of jobs are removed from a sequence and re-inserted into all possible positions of the remaining sequences of jobs, which affects the performance of the algorithm. The basic concept behind the proposed vIG_DE algorithm is to employ differential evolution (DE) to determine two important parameters for the IG algorithm, which are the destruction size and the probability of applying the IG algorithm to an individual. While DE optimizes the destruction size and the probability on a continuous domain by using DE mutation and crossover operators, these two parameters are used to generate a trial individual by directly applying the IG algorithm to each target individual depending on the probability. Next, the trial individual is replaced with the corresponding target individual if it is better in terms of fitness. A unique multi-vector chromosome representation is presented in such a way that the first vector represents the destruction size and the probability, which is a DE vector, whereas the second vector simply consists of a job permutation assigned to each individual in the target population. Furthermore, the traditional IG and a variable IG from the literature are re-implemented as well. The proposed algorithms are applied to the no-idle permutation flowshop scheduling (NIPFS) problem with the makespan and total flowtime criteria. The performances of the proposed algorithms are tested on the Ruben Ruiz benchmark suite and compared to the best-known solutions available at http://soa.iti.es/rruiz as well as to those from a recent discrete differential evolution algorithm (HDDE) from the literature. The computational results show that all three IG variants represent state-of-art methods for the NIPFS problem.     

An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion

An ILS algorithm is proposed to solve the permutation flowshop sequencing problem with total flowtime criterion. The effects of different initial permutations and different perturbation strengths are studied. Comparisons are carried out with three constructive heuristics, three ant-colony algorithms and a particle swarm optimization algorithm. Experiments on benchmarks and a set of random instances show that the proposed algorithm is more effective. The presented ILS improves the best known permutations by a significant margin.     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking

This paper proposes a discrete particle swarm optimization (DPSO) algorithm for the m-machine permutation flowshop scheduling problem with blocking to minimize the makespan, which has a strong industrial background, e.g., many production processes of chemicals and pharmaceuticals in chemical industry can be reduced to this problem. To prevent the DPSO from premature convergence, a self-adaptive diversity control strategy is adopted to diversify the population when necessary by adding a random perturbation to the velocity of each particle according to a probability controlled by the diversity of the current population. In addition, a stochastic variable neighborhood search is used as the local search to improve the search intensification. Computational results using benchmark problems show that the proposed DPSO algorithm outperforms previous algorithms proposed in the literature and that it can obtain 111 new best known upper bounds for the 120 benchmark problems.     

Event-based MILP models for resource-constrained project scheduling problems

In this paper we make a comparative study of several mixed integer linear programming (MILP) formulations for resource-constrained project scheduling problems (RCPSPs).     

Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in permutation flow shop scheduling problems. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on a greedy randomized constructive heuristic, a genetic algorithm (GA) for solution evolution, and a variable neighbourhood search (VNS) to improve the population. The hybridization of a GA with VNS, combining the advantages of these two individual components, is the key innovative aspect of the approach. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high-quality solutions in short computational times. Furthermore, it requires very few user-defined parameters, rendering it applicable to real-life flow shop scheduling problems.     

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.     

Optimal cyclic single crane scheduling for two parallel train oilcan repairing lines

Crane is widely used to move a heavy object from one place to another not only in manufacturing industry but also service industry. As an important resource in the train oilcan repairing, crane scheduling affects directly the productivity of the systems. In this paper, we study cyclic single crane scheduling problem with two parallel train oilcan repairing lines, where jobs are loaded into the line at one end and unloaded at the other end. The processing time at each workstation must be within a given range. There is no buffer between these stations. A crane is used to move jobs between the workstations in two parallel lines. The objective is to schedule the moves to minimize the production cycle. We proposed a time way diagram for two parallel lines and developed a mixed integer linear programming model. Then we extended the model to the scheduling problem with multi-station to eliminate the bottleneck in lines. Examples are given to demonstrate the effectiveness of the model.     

一种快速解决PFSP问题的混合遗传算法

流水车间调度问题属于NP难问题,并且和实际问题联系很紧。但是因为它的解空间太大,一般的算法很容易过早的陷入局部最优或者计算时间太长,提出了一种比较快速的混合遗传算法,能够在很短时间内计算出比较优的结果。详细介绍了这种算法的效果,并与两种常用来解决此类问题的算法进行了比较,总结出了这个算法的特点。     

A hybrid algorithm for the cyclic hoist scheduling problem with two transportation resources

In automated electroplating lines, computer-controlled hoists are used to transfer parts from a processing resource to another one. Products are mounted into carriers and immersed sequentially in a series of tanks following a given sequence.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

Non-permutation flowshop scheduling with dual resources

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.