Real-time scheduling for distributed permutation flowshops with dynamic job arrivals using deep reinforcement learning

Distributed manufacturing plays an important role for large-scale companies to reduce production and transportation costs for globalized orders. However, how to real-timely and properly assign dynamic orders to distributed workshops is a challenging problem. To provide real-time and intelligent decision-making of scheduling for distributed flowshops, we studied the distributed permutation flowshop scheduling problem (DPFSP) with dynamic job arrivals using deep reinforcement learning (DRL). The objective is to minimize the total tardiness cost of all jobs. We provided the training and execution procedures of intelligent scheduling based on DRL for the dynamic DPFSP. In addition, we established a DRL-based scheduling model for distributed flowshops by designing suitable reward function, scheduling actions, and state features. A novel reward function is designed to directly relate to the objective. Various problem-specific dispatching rules are introduced to provide efficient actions for different production states. Furthermore, four efficient DRL algorithms, including deep Q-network (DQN), double DQN (DbDQN), dueling DQN (DlDQN), and advantage actor-critic (A2C), are adapted to train the scheduling agent. The training curves show that the agent learned to generate better solutions effectively and validate that the system design is reasonable. After training, all DRL algorithms outperform traditional meta-heuristics and well-known priority dispatching rules (PDRs) by a large margin in terms of solution quality and computation efficiency. This work shows the effectiveness of DRL for the real-time scheduling of dynamic DPFSP.     

Production scheduling for blocking flowshop in distributed environment using effective heuristics and iterated greedy algorithm

Production scheduling plays an important role in the intelligent decision support system and intelligent optimization decision technology. In the context of the globalization trend, the current production and management may extend from a single factory to a distributed production network. In this paper, we study the distributed blocking flowshop scheduling problem (DBFSP) that is an important generalization of the traditional blocking flowshop scheduling problem in the distributed environment. Six constructive heuristics and an iterated greedy (IG) algorithm are proposed to minimize the makespan, which provides procedures for obtaining efficient and effective solutions to make decision-making sounder. The first five heuristics are developed based on the well-known NEH2 heuristic [B. Naderi, R. Ruiz, The distributed permutation flowshop scheduling problem, Computers & Operations Research, 37 (4) (2010) 754–768.] and the last heuristic is presented by extending the PW heuristic [Q.K. Pan, L. Wang, Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 40 (2) (2012) 218–229.] to DBFSP in an effective way. The composite heuristics that combining constructive heuristics and local searches are also studied. The proposed composite heuristics are chosen to generate an initial solution with a high level of quality. Keeping the simplicity of the IG algorithm, three local search procedures, two destruction procedures, an improved reconstruction procedure, and a simulated annealing-like acceptance criterion are well designed based on the problem-specific knowledge to enhance the IG algorithm. The computational experiments are carried out based on the 720 benchmark instances from the literature. The results show that the proposed heuristics are very effective for solving the problem under consideration and the presented IG algorithm performs significantly better than the other state-of-the-art metaheuristics from the literature.     

Minimizing the total completion time in a distributed two stage assembly system with setup times

In this paper, a novel distributed two stage assembly flowshop scheduling problem (DTSAFSP) is addressed. The objective is to assign jobs to several factories and schedule the jobs in each factory with the minimum total completion time (TCT). In view of the NP-hardness of the DTSAFSP, we develop heuristics method to deal with the problem and propose three hybrid meta-heuristics (HVNS, HGA-RVNS, and HDDE-RVNS). The parameters of HGA-RVNS and HDDE-RVNS are tuned by using the Taguchi method and that of HVNS is done by using the single factor ANOVA method. Computational experiments have been conducted to compare the performances of the proposed algorithms. The analyses of computational results show that, for the instances with small numbers of jobs, HDDE-RVNS obtains better performances than HGA-RVNS and HVNS; whereas for the instances with large numbers of jobs, HGA-RVNS is the best one in all the proposed algorithms. Computational results indicate that the performances of the HDDE-RVNS and HGA-RVNS are not much affected by the number of machines at the first stage and factories. The experimental results also show that the RVNS-based local search steps in both HGA-RVNS and HDDE-RVNS are efficient and effective.     

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

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

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.     

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.     

Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling

Factory management plays an important role in improving the productivity and quality of service in the production process. In particular, the distributed permutation flow shop scheduling problem with multiple factories is considered a priority factor in the factory automation. This study proposes a novel model of the developed distributed scheduling by supplementing the reentrant characteristic into the model of distributed reentrant permutation flow shop (DRPFS) scheduling. This problem is described as a given set of jobs with a number of reentrant layers is processed in the factories, which compromises a set of machines, with the same properties. The aim of the study is to determine the number of factory needs to be used, jobs assignment to certain factory and sequence of job assigned to the factory in order to simultaneously satisfy three objectives of minimizing makespan, total cost and average tardiness. To do this, a novel multi-objective adaptive large neighborhood search (MOALNS) algorithm is developed for finding the near optimal solutions based on the Pareto front. Various destroy and repair operators are presented to balance between intensification and diversification of searching process. The numerical examples of computational experiments are carried out to validate the proposed model. The analytical results on the performance of proposed algorithm are checked and compared with the existing methods to validate the effectiveness and robustness of the proposed potential algorithm in handling the DRPFS problem.     

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.     

Minimizing cost-related objective in synchronous scheduling of parallel factories in the virtual production network

This paper will introduce the Monte Carlo-based heuristic with seven local searches (LSs) which are carefully designed for distributed production network scheduling. Distributed production network consists of the number of different individual factories that joins together to form a network, in which these factories can operate more economically than operating individually and each individual factory usually focuses on self-benefits. Some realistic features such as heterogeny of factories and the transportation among factories are incorporated in our problem definition. However, in such network, each individual factory usually focuses on self-benefits and it plans to optimize its own profit. In this problem, among F exit factories in the network, F′ factories are interested in the total earliness costs and the remaining factories (F″ = F − F′) are interested in the total tardiness cost. Cost minimization is achieved through the minimization of earliness in F′factories, tardiness in F″ factories and the total costs of operation time of all jobs. This algorithm initializes with best known non-cooperative local scheduling and then the LSs search simultaneously through the same solution space, starting from the same current solution. Upon receiving the solutions from the LSs, the new solution will be accepted based on the Monte Carlo acceptance criterion. This criterion always accepts an improved solution and, in order to escape local minima, accept the worse solutions with a certain probability, which this probability decreases with deteriorating solutions. After solving the mixed integer linear programming by the CPLEX solver in the small-size instances, the results obtained by heuristic are compared with two genetic algorithms in the large-size instances. The results of the scheduling before cooperation in production network were also considered in the experiments.     

Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications

The multimedia data objects scheduling problem for WWW applications is modeled using the two-machine flowshop problem of minimizing maximum lateness with separate setup times. We establish three dominance relations, and propose four heuristics. Also, we conduct computational experiments to compare the performance of the proposed heuristics and that of existing ones in the literature. The results of the computational experiments show that the proposed heuristics are quite efficient.Scope and purposeA two-machine flowshop scheduling problem involves scheduling a number of jobs on the machines in order to optimize a given criterion. The majority of research assumes that setup times are negligible or can be combined with the processing times. However, the latter assumption is invalid since it may lead to more idle time on the second machine. In the literature, the separate setup times problem has been mainly addressed with the completion-time-related objective functions such as makespan. However, there are many real-life situations in which a due-date-related objective function such as maximum lateness is more appropriate. The problem with maximum lateness objective has received limited attention from researchers as indicated by a recent survey paper. In this paper, we show a real-life situation in the Internet where the two-machine flowshop problem of minimizing maximum lateness with separate setup times can be used to model the multimedia object scheduling problem. We propose new improved heuristics for this problem and compare with existing ones in the literature.     

An efficient stochastic hybrid heuristic for flowshop scheduling

The paper addresses the problem of flowshop scheduling in order to minimize the makespan objective. Three probabilistic hybrid heuristics are presented for solving permutation flowshop scheduling problem. The proposed methodology combines elements from both constructive heuristic search and a stochastic improvement technique. The stochastic method used in this paper is simulated annealing (SA). Experiments have been run on a large number of randomly generated test problems of varying jobs and machine sizes. Our approach is shown to outperform best-known existing heuristics, including the classical NEH technique (OMEGA, 1983) and the SA based on (OMEGA, 1989) of Osman and Potts . Statistical tests of significance are performed to substantiate the claims of improvement.     

Permutation flowshop scheduling problems with maximal and minimal time lags

In this paper, we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m$m$-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.     

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 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.     

Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness

In this paper we address the problem of scheduling jobs in a permutation flowshop with a just-in-time objective, i.e. the minimisation of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specific instance to be solved. After an in-depth analysis of the problem, different cases or sub-problems are identified and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three different local search procedures that use the proposed constructive heuristic as initial solution.The proposed Prod. Type: FLPheuristics have been compared on an extensive set of instances with the best-so-far heuristic for the problem, as well as with adaptations of efficient heuristics for similar scheduling problems. The computational results show the excellent performance of the proposed algorithms. Finally, the positive impact of the efficient heuristics is evaluated by including them as seed sequences for one of the best metaheuristic for the problem.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

Impact of permutation enforcement when minimizing total weighted tardiness in dynamic flowshops with uncertain processing times

This paper is motivated by the problem of meeting due dates in a flowshop production environment with jobs with different weights and uncertain processing times. Enforcement of a permutation schedule to varying degrees for dynamic flowshops is investigated with the goal of minimizing total weighted tardiness (TWT). The approaches studied are categorized as follows: (1) pure permutation scheduling (2) shift-based scheduling (3) pure dispatching (which leads to non-permutation sequences). A simulation-based experimental study was carried out to study the performance of the above methods with respect to minimizing TWT when new jobs arrive to the flowshop at every shift change. Results indicate significant gains in performance are possible when the permutation requirement is relaxed and shift-based scheduling is allowed. Shift-based scheduling yields competitive results with respect to the pure dispatching approach, even though dispatching has the advantage of a full relaxation of the permutation requirement.     

Ant colony optimization algorithm for a Bi-criteria 2-stage hybrid flowshop scheduling problem

We consider the problem of scheduling jobs in a hybrid flowshop with two stages. Our objective is to minimize both the makespan and the total completion time of jobs. This problem has been little studied in the literature. To solve the problem, we propose an ant colony optimization procedure. Computational experiments are conducted using random-generated instances from the literature. In comparison against other well-known heuristics from the literature, experimental results show that our algorithm outperforms such 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.     

Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem

This paper addresses a novel distributed assembly permutation flowshop scheduling problem that has important applications in modern supply chains and manufacturing systems. The problem considers a number of identical factories, each one consisting of a flowshop for part-processing plus an assembly line for product-processing. The objective is to minimize the makespan. To suit the needs of different CPU time and solution quality, we present a mixed integer linear model, three constructive heuristics, two variable neighborhood search methods, and an iterated greedy algorithm. Important problem-specific knowledge is obtained to enhance the effectiveness of the algorithms. Accelerations for evaluating solutions are proposed to save computational efforts. The parameters and operators of the algorithms are calibrated and analyzed using a design of experiments. To prove the algorithms, we present a total of 16 adaptations of other well-known and recent heuristics, variable neighborhood search algorithms, and meta-heuristics for the problem and carry out a comprehensive set of computational and statistical experiments with a total of 810 instances. The results show that the proposed algorithms are very effective and efficient to solve the problem under consideration as they outperform the existing methods by a significant margin.