A simulated annealing with multiple‐search paths and parallel computation for a comprehensive flowshop scheduling problem

Recent studies have demonstrated that the performance of a simulated annealing algorithm can be improved by following multiple‐search paths and parallel computation. In this paper, we use these strategies to solve a comprehensive mathematical model for a flexible flowshop lot streaming problem. In the flexible flowshop environment, a number of jobs will be processed in several consecutive production stages, and each stage may involve a certain number of parallel machines that may not be identical. Each job has to be split into several unequal sublots by following the concept of lot streaming. The sublots are to be processed in the order of the stages, and sublots of certain products may skip some stages. This complex problem also incorporates sequence‐dependent setup times, the anticipatory or nonanticipatory nature of setups, release dates for machines, and machine eligibility. Numerical examples are presented to demonstrate the effectiveness of lot streaming in hybrid flowshops, the performance of the proposed simulated annealing algorithm, and the improvements achieved using parallel computation.     

A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry

This paper studies a solar cell industry scheduling problem, which is similar to traditional hybrid flowshop scheduling (HFS). In a typical HFS problem, the allocation of machine resources for each order should be scheduled in advance. However, the challenge in solar cell manufacturing is the number of machines that can be adjusted dynamically to complete the job. An optimal production scheduling model is developed to explore these issues, considering the practical characteristics, such as hybrid flowshop, parallel machine system, dedicated machines, sequence independent job setup times and sequence dependent job setup times. The objective of this model is to minimise the makespan and to decide the processing sequence of the orders/lots in each stage, lot-splitting decisions for the orders and the number of machines used to satisfy the demands in each stage. From the experimental results, lot-splitting has significant effect on shortening the makespan, and the improvement effect is influenced by the processing time and the setup time of orders. Therefore, the threshold point to improve the makespan can be identified. In addition, the model also indicates that more lot-splitting approaches, that is, the flexibility of allocating orders/lots to machines is larger, will result in a better scheduling performance.     

An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan

This paper deals with a variant of flowshop scheduling, namely, the hybrid or flexible flowshop with sequence dependent setup times. This type of flowshop is frequently used in the batch production industry and helps reduce the gap between research and operational use. This scheduling problem is NP-hard and solutions for large problems are based on non-exact methods. An improved genetic algorithm (GA) based on software agent design to minimise the makespan is presented. The paper proposes using an inherent characteristic of software agents to create a new perspective in GA design. To verify the developed metaheuristic, computational experiments are conducted on a well-known benchmark problem dataset. The experimental results show that the proposed metaheuristic outperforms some of the well-known methods and the state-of-art algorithms on the same benchmark problem dataset.     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.     

Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

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.     

Scheduling and Lot Streaming in Flowshops with No-Wait in Process

Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results.     

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.     

A two-stage hybrid flowshop scheduling problem in machine breakdown condition

This paper considers a two-stage hybrid flowshop scheduling problem in machine breakdown condition. By machine breakdown condition we mean that the machine may not always be available during the scheduling period. Machine failure may occur with a known probability after completing a job. Probability of machine failure depends on the previous processed job. The problem to be studied has one machine at the first stage and M parallel identical machines at the second stage. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem is compatible with a large scope of real world situations. To solve the problem, first, we introduce one optimal approach for job precedence when there is one machine in both stages and then provide a heuristic algorithm when there are M machines in stage two. To examine the performance of the heuristic, some experiments used are provided as well.     

Hybrid flowshop scheduling with sequence‐dependent setup times by hybridizing max–min ant system,simulated annealing and variable neighbourhood search

This paper deals with the hybrid flowshop scheduling problems with sequence‐dependent setup times. To minimize the makespan, we propose hybrid metaheuristic approach, which integrates several features from ant colony optimization, simulated annealing and variable neighbourhood search in a new configurable scheduling algorithm. Our proposed algorithms are tuned by means of design of experiments approach. We present computational experiments on standard test problems and compare the results with the several algorithms presented previously. The results illustrate that the hybrid metaheuristic outperforms the other algorithms.     

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.     

The production scheduling problem in a multi-page invoice printing system

This paper addresses the production scheduling problem in a multi-page invoice printing system. The system comprises three stages: the stencil preparation stage, the page printing stage and the invoice assembly stage. Since each page can be considered as a component and the invoice as the finished product, the production system for multi-page invoices can be treated as an assembly-type flowshop with parallel machines at the last two stages. Moreover, two types of sequence-dependent setup operations are considered at the second stage. The objective is to minimize the makespan for all the invoice orders. We first formulate this problem into a mixed-integer linear programming (MILP). Then a hybrid genetic algorithm (HGA) is proposed for solving it due to its NP-hardness. To evaluate the performance of the HGA heuristic, a lower bound for the makespan is developed. Numerical experiment indicates that our algorithm can solve the problem efficiently and effectively.     

Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times

In this paper we consider a multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times by minimizing total weighted tardiness and maximum completion time simultaneously. Whereas these kinds of problems are NP-hard, thus we proposed a multi-population genetic algorithm (MPGA) to search Pareto optimal solution for it. This algorithm comprises two stages. First stage applies combined objective of mentioned objectives and second stage uses previous stage’s results as an initial solution. In the second stage sub-population will be generated by re-arrangement of solutions of first stage. To evaluate performance of the proposed MPGA, it is compared with two distinguished benchmarks, multi-objective genetic algorithm (MOGA) and non-dominated sorting genetic algorithm II (NSGA-II), in three sizes of test problems: small, medium and large. The computational results show that this algorithm performs better than them.     

A note on two-stage hybrid flowshop scheduling with missing operations

The scheduling problem in a multi-stage hybrid flowshop has been the subject of considerable research. All the studies on this subject assume that each job has to be processed on all the stages, i.e., there are no missing operations for a job at any stage. However, missing operations usually exist in many real-life production systems, such as a system in a stainless steel factory investigated in this note. The studied production system in the factory is composed of two stages in series. The first stage contains only one machine while the second stage consists of two identical machines (namely a 1 × 2 hybrid flowshop). In the system, some jobs have to be processed on both stages, but others need only to be processed on the second stage. Accordingly, the addressed scheduling problem is a 1 × 2 hybrid flowshop with missing operations at the first stage. In this note, we develop a heuristic for the problem to generate a non-permutation schedule (NPS) from a given permutation schedule, with the objective of minimizing the makespan. Computational results demonstrate that the heuristic can efficiently generate better NPS solutions.     

A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties

Recently introduced colonial competitive algorithm (CCA) has shown its excellent capability on different optimization problems. The aim of this paper is to propose a discrete version of this method to determine a schedule that minimizes sum of the linear earliness and quadratic tardiness in the hybrid flowshops scheduling problem with simultaneously considering effects of sequence-dependent setup times and limited waiting time. In other word we assume that the waiting time for each job between two consecutive stages cannot be greater than a given upper bound. Also for this problem, a mixed integer program is formulated. Computational results are presented to evaluate the performance of the proposed algorithms for problems with different structures.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

A Discrete Inter-Species Cuckoo Search for flowshop scheduling problems

This paper presents a discrete version of the Inter-Species Cuckoo Search (ISCS) algorithm and illustrates its use for solving two significant types of the flow-shop scheduling problems. These are Hybrid Flow-shop Scheduling (HFS) and Permutation Flow-shop Sequencing Problems (PFSP). Hybrid flowshop scheduling problems are a generalization of flowshops having parallel machines in some stages and these problems are known to be NP-hard. A heuristic rule called the Smallest Position Value (SPV) is used to enable the continuous inter-species cuckoo search to be applied to most types of sequencing problems. Makespan and mean flow time are the objective functions considered and computational experiments are carried out to compare the proposed Discrete Inter-Species Cuckoo Search (DISCS) with other state-of-the-art meta-heuristic algorithms. Experimental results confirm the superiority of DISCS with respect to many other existing metaheuristic search algorithms.     

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.