Scatter search for mixed blocking flowshop scheduling

Empty or limited storage capacities between machines introduce various types of blocking constraint in the industries with flowshop environment. While large applications demand flowshop scheduling with a mix of different types of blocking, research in this area mainly focuses on using only one kind of blocking in a given problem instance. In this paper, using makespan as a criterion, we study permutation flowshops with zero capacity buffers operating under mixed blocking conditions. We present a very effective scatter search (SS) algorithm for this. At the initialisation phase of SS, we use a modified version of the well-known Nawaz, Enscore and Ham (NEH) heuristic. For the improvement method in SS, we use an Iterated Local Search (ILS) algorithm that adopts a greedy job selection and a powerful NEH-based perturbation procedure. Moreover, in the reference set update phase of SS, with small probabilities, we accept worse solutions so as to increase the search diversity. On standard benchmark problems of varying sizes, our algorithm very significantly outperforms well-known existing algorithms in terms of both the solution quality and the computing time. Moreover, our algorithm has found new upper bounds for 314 out of 360 benchmark problem instances.     

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.     

Sequencing and Scheduling in Robotic Cells: Recent Developments

A great deal of work has been done to analyze the problem of robot move sequencing and part scheduling in robotic flowshop cells. We examine the recent developments in this literature. A robotic flowshop cell consists of a number of processing stages served by one or more robots. Each stage has one or more machines that perform that stage’s processing. Types of robotic cells are differentiated from one another by certain characteristics, including robot type, robot travel-time, number of robots, types of parts processed, and use of parallel machines within stages. We focus on cyclic production of parts. A cycle is specified by a repeatable sequence of robot moves designed to transfer a set of parts between the machines for their processing.We start by providing a classification scheme for robotic cell scheduling problems that is based on three characteristics: machine environment, processing restrictions, and objective function, and discuss the influence of these characteristics on the methods of analysis employed. In addition to reporting recent results on classical robotic cell scheduling problems, we include results on robotic cells with advanced features such as dual gripper robots, parallel machines, and multiple robots. Next, we examine implementation issues that have been addressed in the practice-oriented literature and detail the optimal policies to use under various combinations of conditions. We conclude by describing some important open problems in the field.     

A genetic algorithm with genes-association recognition for flowshop scheduling problems

In this paper, we consider a flowshop scheduling problem with a special blocking RCb (Release when Completing Blocking). This flexible production system is prevalent in some industrial environments. Genetic algorithms are first proposed for solving these flowshop problems and different initial populations have been tested to find which is best adapted. Then, a method is proposed for further improving genetic algorithm found solutions, which consists in marking out recurrent genes association occurrences in an already genetic algorithm optimized population. This idea directly follows Holland’s first statement about nature observations. Here, proposed idea is that populations well adapted to a problem have an adapted genetic code with common properties. We propose to mark out these properties in available genetic code to further improve genetic algorithm efficiency. Implementation of this method is presented and obtained results on flowshop scheduling problems are discussed.     

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.     

Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.     

Multi-degree cyclic scheduling of two robots in a no-wait flowshop

This paper addresses multi-degree cyclic scheduling of two robots in a no-wait flowshop, where exactly r(r > 1) identical parts with constant processing times enter and leave the production line during each cycle, and transportation of the parts between machines is performed by two robots on parallel tracks. The objective is to minimize the cycle time. The problem is transformed into enumeration of pairs of overlapping moves that cannot be performed by the same robot. This enumeration is accomplished by enumerating intervals for some linear functions of decision variables. The algorithm developed is polynomial in the number of machines for a fixed r, but exponential if r is arbitrary. Computational results with benchmark instances are reported. Note to Practitioners-This paper was motivated by the problem of cyclic scheduling of a no-wait production line, where a part must be processed without any interruption either on or between machines due to characteristics of the processing technology itself or the absences of storage capacity between operations of a part. Multi-degree schedules, in which multiple parts enter and leave the line during a cycle, usually have larger throughput rate than simple ones. This paper proposes an algorithm for multi-degree cyclic scheduling of a no-wait flowshop with two robots. Computational results show that the throughput rate can be really improved by using multi-degree schedules with two robots. However, we have not addressed the decision of the optimal value of the degree of the cycle. Furthermore, since we consider that the two robots travel along parallel tracks, the collision-avoidance constraints have been relaxed in the algorithm. In future research, we will address the two problems and generalize the algorithm to multi-robot cases.     

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.     

The optimal number of used machines in a two-stage flexible flowshop scheduling problem

We study practical scheduling problems with a major decision referring to the number of machines to be used. We focus on a two-stage flexible flowshop, where each job is processed on the first (critical) machine, and then continues to one of the second-stage parallel machines. Jobs are assumed to have identical processing times, and are processed in batches. A setup time is required when starting a new batch. We consider two objective functions: minimum makespan and minimum flowtime. In both cases, a closed form expression for the optimal number of machines to be used is introduced, and a unique and unusual sequence of decreasing batch sizes is shown to be optimal.     

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.     

Throughput optimization in two-machine flowshops with flexible operations

In this study, a two-machine flowshop producing identical parts is considered. Each of the identical parts is assumed to require a number of manufacturing operations, and the machines are assumed to be flexible enough to perform different operations. Due to economical or technological constraints, some specific operations are preassigned to one of the machines. The remaining operations, called flexible operations, can be performed on either one of the machines, so that the same flexible operation can be performed on different machines for different parts. The problem is to determine the assignment of the flexible operations to the machines for each part, with the objective of maximizing the throughput rate. We consider various cases regarding the number of parts to be produced and the capacity of the buffer between the machines. We present solution methods for each variant of the problem.     

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.     

Scheduling flow lines with buffers by ant colony digraph

This work starts from modeling the scheduling of n jobs on m machines/stages as flowshop with buffers in manufacturing. A mixed-integer linear programing model is presented, showing that buffers of size n ? 2 allow permuting sequences of jobs between stages. This model is addressed in the literature as non-permutation flowshop scheduling (NPFS) and is described in this article by a disjunctive graph (digraph) with the purpose of designing specialized heuristic and metaheuristics algorithms for the NPFS problem. Ant colony optimization (ACO) with the biologically inspired mechanisms of learned desirability and pheromone rule is shown to produce natively eligible schedules, as opposed to most metaheuristics approaches, which improve permutation solutions found by other heuristics. The proposed ACO has been critically compared and assessed by computation experiments over existing native approaches. Most makespan upper bounds of the established benchmark problems from Taillard (1993) and Demirkol, Mehta, and Uzsoy (1998) with up to 500 jobs on 20 machines have been improved by the proposed ACO.     

A new heuristic and dominance relations for no-wait flowshops with setups

The two-machine no-wait flowshop problem, where setup times are considered separate from processing times and sequence independent, is addressed with respect to minimizing total flowtime. A local and a global dominance relation are developed and a new heuristic is provided. Furthermore, a lower bound is obtained and used along with the dominance relations in a branch-and-bound algorithm in order to evaluate the efficiency of the heuristic. Computational experience demonstrates the superiority of the local dominance relation and the new heuristic.Scope and purposeNo-wait flowshop problems, where jobs have to be processed without interruption between consecutive machines, represent an important area in scheduling. There are several industries where the no-wait flowshop problem applies including the metal, plastic, and chemical industries. For instance, in the case of steel production, the heated metal must continuously go through a sequence of operations before it is cooled in order to prevent defects in the composition of the material. Another important area arises when setup time is considered separate from processing time. Such a consideration is particularly justified when the ratio of setup to processing time is non-negligible. Many applications warrant separate consideration of setup; examples include the re-tooling of multi-tool equipment. Other applications can be found in textile, plastic, chemical, and semi-conductor industries. This paper develops a new heuristic and dominance relations for the two-machine no-wait separate setup flowshop problem, where the performance criterion is total flowtime.     

时间约束混合流水车间调度问题综述

车间调度是智能制造领域中的核心问题之一, 在经典流水车间调度中, 所有工件按照相同的加工顺序在指 定机床上加工. 混合流水车间调度(HFS)作为流水车间调度的特例, 相比前者增加了机床选择的灵活性, 可以显著 优化系统目标, 但同时也增加了问题求解的难度. 由于时间约束HFS相比基本HFS问题更贴近实际生产过程, 近年 来, 综合考虑各类时间相关约束的HFS问题得到了深入研究. 因此, 本文围绕基本HFS、有限等待时间HFS、带准备 时间HFS、模糊/随机加工时间HFS、多时间约束HFS、时间约束相关多目标HFS等问题开展研究. 针对每一类时间 约束HFS问题, 按照问题规模对当前研究成果进行分类描述, 按照确定性算法、启发式方法、元启发式方法、算法混 合对相关成果进行算法分类, 按照实际工业应用对文献进行归类分析. 另一方面, 围绕交货期、能耗、成本等3类性 能指标, 分析了在各类时间约束HFS问题中的多目标优化相关成果. 最后详细分析了带时间约束HFS问题在问题层 面、算法层面和应用层面存在的挑战性问题和未来研究的方向.     

Stochastic proportionate flowshop scheduling with setups

This paper addresses the problem of scheduling n jobs on a proportionate two-machine flowshop where the machines are subject to random breakdowns and setup times are considered separate from processing times. The considered performance measure is makespan. Sequences that minimize makespan with probability 1 are obtained when the first or the second machine is subject to random breakdowns without making any assumptions about downtime distributions or counting processes. It is assumed that the processing and setup times on one machine dominate the corresponding times on the other machine. In the case that processing and setup times on the first and second machines are proportionate, it is shown that the longest processing time (LPT) rule gives an optimal solution when only the first machine is subject to breakdowns, while the shortest processing time (SPT) rule yields an optimal solution when only the second machine suffers breakdowns.     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

A cooperative dispatching approach for minimizing mean tardiness in a dynamic flowshop

Cooperative Dispatching is a real-time scheduling methodology, which consults downstream machines before making a job dispatching decision on any given machine. This paper proposes such an approach for minimizing the mean tardiness in a dynamic flowshop where new jobs arrive continuously, at random points in time, throughout the production cycle. Cooperative Dispatching is based on the idea that individual machines act self-interestedly, with the objective of optimizing their local performance criteria. A consulted machine attempts to influence upstream dispatching decisions in a manner that promotes its ability to minimize its total local tardiness. A machine's influence in the dispatching decision depends on current congestion and due-date tightness levels in the shop. A multiple regression model is proposed to help determine the weight a consulted machine's preferences will carry in the dispatching decision. Conflicting demands from the different machines are resolved by a minimum regret decision procedure, which aims to minimize the aggregate deviation from the consulted machines' preferences. The winning candidate that ultimately emerges from this procedure is the job that is dispatched. A comparative analysis to evaluate the performance of cooperative dispatching, compared to six other dispatching rules that are commonly favoured for tardiness-based criteria, is performed by means of simulation, using randomly generated test problems. Computational results indicate that Cooperative Dispatching outperforms the other dispatching rules, across a broad range of flowshop congestion and due-date tightness levels.     

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.     

Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics

In this paper, we address the problem of scheduling a set of jobs in a flowshop with makespan objective. In contrast to the usual assumption of machine availability presented in most research, we consider that machines may not be available at the beginning of the planning period, due to processing of previously scheduled jobs. We first formulate the problem, analyse the structure of solutions depending on a number of factors (such as machines, jobs, structure of the processing times, availability vectors, etc.), and compare it with its classical counterpart. Results indicate that the problem under consideration presents a different structure of solutions, and that it is easier than the classical permutation flowshop problem. In view of these results, we propose and test a number of fast heuristics for the problem.