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.     

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.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided.     

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.     

A discrete differential evolution algorithm for the permutation flowshop scheduling problem

Very recently, Pan et al. [Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO07, pp. 126–33] presented a new and novel discrete differential evolution algorithm for the permutation flowshop scheduling problem with the makespan criterion. On the other hand, the iterated greedy algorithm is proposed by [Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–49] for the permutation flowshop scheduling problem with the makespan criterion. However, both algorithms are not applied to the permutation flowshop scheduling problem with the total flowtime criterion. Based on their excellent performance with the makespan criterion, we extend both algorithms in this paper to the total flowtime objective. Furthermore, we propose a new and novel referenced local search procedure hybridized with both algorithms to further improve the solution quality. The referenced local search exploits the space based on reference positions taken from a reference solution in the hope of finding better positions for jobs when performing insertion operation. Computational results show that both algorithms with the referenced local search are either better or highly competitive to all the existing approaches in the literature for both objectives of makespan and total flowtime. Especially for the total flowtime criterion, their performance is superior to the particle swarm optimization algorithms proposed by [Tasgetiren, M. F., Liang, Y. -C., Sevkli, M., Gencyilmaz, G. (2007). Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930–47] and [Jarboui, B., Ibrahim, S., Siarry, P., Rebai, A. (2007). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, doi:10.1016/j.cie.2007.09.006]. Ultimately, for Taillard’s benchmark suite, four best known solutions for the makespan criterion as well as 40 out of the 90 best known solutions for the total flowtime criterion are further improved by either one of the algorithms presented in this paper.     

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.     

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.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem

Scheduling with learning effects has gained increasing attention in recent years. A well‐known learning model is called “sum‐of‐processing‐times‐based learning” in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Moreover, the concept of learning process is relatively unexplored in a flowshop environment. Motivated by these observations, this article addresses a two‐machine flowshop problem with a truncated learning effect. The objective is to find an optimal schedule to minimize the total completion time. First, a branch‐and‐bound algorithm incorporating with a dominance property and four lower bounds is developed to derive the optimal solution. Then three simulated annealing algorithms are also proposed for near‐optimal solution. The experimental results indicated that the branch‐and‐bound algorithm can solve instances up to 18 jobs, and the proposed simulated annealing algorithm performs well in item of CPU time and error percentage. © 2011 Wiley Periodicals, Inc.     

A simheuristic algorithm to set up starting times in the stochastic parallel flowshop problem

This paper addresses the parallel flowshop scheduling problem with stochastic processing times, where a product composed of several components has to be finished at a particular moment. These components are processed in independent parallel factories, and each factory can be modeled as a permutation flowshop. The processing time of each operation at each factory is a random variable following a given probability distribution. The aim is to find the robust starting time of the operations at each factory in a way that all the components of the product are completed on a given deadline with a user-defined probability. A simheuristic algorithm is proposed in order to minimize each of the following key performance indicators: (i) the makespan in the deterministic version; and (ii) the expected makespan or a makespan percentile in the stochastic version. A set of computational experiments are carried out to illustrate the performance of the proposed methodology by comparing the outputs under different levels of stochasticity.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

Minimizing makespan in three-machine flow shops with deteriorating jobs

In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently.     

A hybrid estimation of distribution algorithm for simulation-based scheduling in a stochastic permutation flowshop

The permutation flowshop scheduling problem (PFSP) is NP-complete and tends to be more complicated when considering stochastic uncertainties in the real-world manufacturing environments. In this paper, a two-stage simulation-based hybrid estimation of distribution algorithm (TSSB-HEDA) is presented to schedule the permutation flowshop under stochastic processing times. To deal with processing time uncertainty, TSSB-HEDA evaluates candidate solutions using a novel two-stage simulation model (TSSM). This model first adopts the regression-based meta-modelling technique to determine a number of promising candidate solutions with less computation cost, and then uses a more accurate but time-consuming simulator to evaluate the performance of these selected ones. In addition, to avoid getting trapped into premature convergence, TSSB-HEDA employs both the probabilistic model of EDA and genetic operators of genetic algorithm (GA) to generate the offspring individuals. Enlightened by the weight training process of neural networks, a self-adaptive learning mechanism (SALM) is employed to dynamically adjust the ratio of offspring individuals generated by the probabilistic model. Computational experiments on Taillard’s benchmarks show that TSSB-HEDA is competitive in terms of both solution quality and computational performance.     

Flowshop scheduling with a general exponential learning effect

This paper investigates flowshop scheduling problems with a general exponential learning effect, i.e., the actual processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The objective is to minimize the makespan, the total (weighted) completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times, respectively. Several simple heuristic algorithms are proposed in this paper by using the optimal schedules for the corresponding single machine problems. The tight worst-case bound of these heuristic algorithms is also given. Two well-known heuristics are also proposed for the flowshop scheduling with a general exponential learning effect.     

Exact and parallel metaheuristic algorithms for the single processor total weighted completion time scheduling problem with the sum-of-processing-time based models

In this paper, the single processor scheduling problem to minimize the total weighted completion times is analysed, where the processing times of jobs are described by functions dependent on the sum of the normal processing times of previously processed jobs, which can model learning or aging (deteriorating) effects. We construct the exact pseudopolynomial time algorithm based on the dynamic programming, which solves the problem, where the processing time of each job is described by an arbitrary stepwise function. Moreover, the parallel metaheuristic algorithms are provided for the general version of the problem with arbitrary sum-of-processing time based models. The efficiency of the proposed algorithms is evaluated during numerical analysis.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups

This paper considers the problem of scheduling part families and jobs within each part family in a flowshop manufacturing cell with sequence dependent family setups times where it is desired to minimize the makespan while processing parts (jobs) in each family together. Two evolutionary algorithms—a Genetic Algorithm and a Memetic Algorithm with local search—are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. The proposed algorithms use a compact representation for the solution and a hierarchically structured population where the number of possible neighborhoods is limited by dividing the population into clusters. In comparison to a Multi-Start procedure, solutions obtained by the proposed evolutionary algorithms were very close to the lower bounds for all problem instances. Moreover, the comparison against the previous best algorithm, a heuristic named CMD, indicated a considerable performance improvement.     

两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度。分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解。最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。     

A note on machine scheduling with sum-of-logarithm-processing-time-based and position-based learning effects

Recently, Biskup [2] classifies the learning effect models in scheduling environments into two types: position-based and sum-of-processing-time-based. In this paper, we study scheduling problem with sum-of-logarithm-processing-time-based and position-based learning effects. We show that the single machine scheduling problems to minimize the makespan and the total completion time can both be solved by the smallest (normal) processing time first (SPT) rule. We also show that the problems to minimize the maximum lateness, the total weighted completion times and the total tardiness have polynomial-time solutions under agreeable WSPT rule and agreeable EDD rule. In addition, we show that m-machine permutation flowshop problems are still polynomially solvable under the proposed learning model.     

Online batch scheduling on parallel machines with delivery times

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).