A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates

Flexible job shop scheduling problem (FJSSP) is generalization of job shop scheduling problem (JSSP), in which an operation may be processed on more than one machine each of which has the same function. Most previous researches on FJSSP assumed that all jobs to be processed are available at the beginning of scheduling horizon. The assumption, however, is always violated in practical industries because jobs usually arrive over time and can not be predicted before their arrivals. In the paper, dynamic flexible job shop scheduling problem (DFJSSP) with job release dates is studied. A heuristic is proposed to implement reactive scheduling for the dynamic scheduling problem. An approach based on gene expression programming (GEP) is also proposed which automatically constructs reactive scheduling policies for the dynamic scheduling. In order to evaluate the performance of the reactive scheduling policies constructed by the proposed GEP-based approach under a variety of processing conditions three factors, such as the shop utilization, due date tightness, problem flexibility, are considered in the simulation experiments. The scheduling performance measure considered in the simulation is the minimization of makespan, mean flowtime and mean tardiness, respectively. The results show that GEP-based approach can construct more efficient reactive scheduling policies for DFJSSP with job release dates under a big range of processing conditions and performance measures in the comparison with previous approaches.     

Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: an optimization via simulation approach

This paper presents an optimization via simulation approach to solve dynamic flexible job shop scheduling problems. In most real-life problems, certain operation of a part can be processed on more than one machine, which makes the considered system (i.e., job shops) flexible. On one hand, flexibility provides alternative part routings which most of the time relaxes shop floor operations. On the other hand, increased flexibility makes operation machine pairing decisions (i.e., the most suitable part routing) much more complex. This study deals with both determining the best process plan for each part and then finding the best machine for each operation in a dynamic flexible job shop scheduling environment. In this respect, a genetic algorithm approach is adapted to determine best part processing plan for each part and then select appropriate machines for each operation of each part according to the determined part processing plan. Genetic algorithm solves the optimization phase of solution methodology. Then, these machine-operation pairings are utilized by discrete-event system simulation model to estimate their performances. These two phases of the study follow each other iteratively. The goal of methodology is to find the solution that minimizes total of average flowtimes for all parts. The results reveal that optimization via simulation approach is a good way to cope with dynamic flexible job shop scheduling problems, which usually takes NP-Hard form.     

共生进化算法母体选择策略性能研究及改进

轮盘赌在传统遗传算法中能加快进化速度和提高解质量,以共生进化算法求解一个复杂的柔性作业调度为例,跟踪共生种群进化过程。研究轮盘赌在以求得最优组合为目标的共生进化算法中对种群进化速度、种群多样性以及解质量的影响。为提高种群进化的解质量,引入了Worst策略。仿真实验表明,轮盘赌在共生进化算法中的应用不能促进解质量的提高,Worst策略能有效调节种群的进化速度并能提升解质量。     

Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines

The flexibilities of alternative process plans and unrelated parallel machines are benefit for the optimization of the job shop scheduling problem, but meanwhile increase the complexity of the problem. This paper constructs the mathematical model for the multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines, splits the problem into two sub-problems, namely flexible processing route decision and task sorting, and proposes a two-generation (father and children) Pareto ant colony algorithm to generate a feasible scheduling solution. The father ant colony system solves the flexible processing route decision problem, which selects the most appropriate process node set from the alternative process node set. The children ant colony system solves the sorting problem of the process task set generated by the father ant colony system. The Pareto ant colony system constructs the applicable pheromone matrixes and heuristic information with respect to the sub-problems and objectives. And NSGAII is used as comparison whose genetic operators are re-defined. The experiment confirms the validation of the proposed algorithm. By comparing the result of the algorithm to NSGAII, we can see the proposed algorithm has a better performance.     

Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line

A reentrant hybrid flow shop, typically found in the electronics industry, is an extended system of the ordinary flow shop in such a way that there exist one or more parallel machines at each serial stage and each job has the reentrant product flow, i.e., a job may visit a stage several times. Among the operational issues in reentrant hybrid flow shops, we focus on the scheduling problem that determines the allocation of jobs to the machines at each stage as well as the sequence of the jobs assigned to each machine. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a real-time scheduling mechanism with a decision tree when selecting appropriate dispatching rules. The decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported for various system performance measures.     

Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem

This paper presents a simulated annealing algorithm accelerated by a partial scheduling mechanism and a cooling schedule mechanism that is a function of the standard deviation. This facilitates a rapid approach to good solutions in the flexible job shop scheduling problem (FJSSP). The results demonstrate that for benchmark instances of several sizes, simulated annealing that implements the proposed mechanism converges more quickly to good solutions than simulated annealing that does not implement the proposed mechanism.     

Double Layer ACO Algorithm for the Multi-Objective FJSSP

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. In this work, a double layer Ant Colony Optimization (ACO) algorithm is proposed for the Flexible Job Shop Scheduling Problem (FJSSP). In the proposed algorithm, two different ACO algorithms are applied to solve the FJSSP with a hierarchical way. The primary mission of upper layer ACO algorithm is achieving an excellent assignment of operations to machines. The leading task of lower layer ACO algorithm is obtaining the optimal sequencing of operations on each machine. Experimental results suggest that the proposed algorithm is a feasible and effective approach for the multi-objective FJSSP.

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

Distributed bottleneck control for repetitive production systems

A bottleneck control problem for general periodic job shops with blocking where each machine has an input buffer of finite capacity is investigated. The job shop considered consists of a set of workflows competing with each other for access to common machines. A distributed buffer control policy that restricts a job entering an input buffer of a local machine in a specific sequence is proposed. The conditions sufficient for design and allocation of dispatching rules are presented. The system time and the rate of machine utilization are considered as the evaluation criteria. Finally, the procedure aimed at scheduling periodic job shops is provided.     

A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop

This paper presents a genetic algorithm-based job-shop scheduler for a flexible multi-product, parallel machine sheet metal job shop. Most of the existing research has focused only on permutation job shops in which the manufacturing sequence and routings are strictly in a predefined order. This effectively meant that only the jobs shops with little or no flexibility could be modeled using these models. The real life job shops may have flexibility of routing and sequencing. Our paper proposes one such model where variable sequences and multiple routings are possible. Another limitation of the existing literature was found to be negligence of the setup times. In many job shops like sheet metal shops, setup time may be a very sizable portion of the total make-span of the jobs, hence setup times will be considered in this work. One more flexibility type arises as a direct consequence of the routing flexibility. When there are multiple machines (parallel machines) to perform the same operation, the job could be routed to one or more of these machines to reduce the make-span. This is possible in situations where each job consists of a pre-defined quantity of a specified product. In other words, same job is quantity-wise split into two or more parts whenever it reduces the makespan. This effectively assumes that the setup cost is negligible. This model has been implemented on a real-life industry problem using VB.Net programming language. The results from the scheduler are found to be better than those obtained by simple sequencing rules.     

Job shop scheduling heuristics for sequence dependent setups

In this paper we develop a more realistic algorithm which addresses the job shop scheduling problem with sequence dependent setup times, and some complex constraints such as multiple machines, multiple resources, and alternate routes; then, we evaluate the performance of the algorithm relative to the performance criteria used in the real world shops. To illustrate the potential impact of addressed problem, we simulate the scheduling jobs using three different approaches under a variety of conditions. Experimental designs are used to find the difference among these approaches, and to justify the value of the more realistic approach.     

Joint optimization of job scheduling and maintenance planning for a two-machine flow shop considering job-dependent operating condition

Two-machine flow shops are widely adopted in manufacturing systems. To minimize the makespan of a sequence of jobs, joint optimization of job scheduling and preventive maintenance (PM) planning has been extensively studied for such systems. In practice, the operating condition (OC) of the two machines usually varies from one job to another because of different processing covariates, which directly affects the machines’ failure rates, PM plans, and expected job completion times. This fact is common in many real systems, but it is often overlooked in the related literature. In this study, we propose a joint decision-making strategy for a two-machine flow shop with resumable jobs. The objective is to minimize the expected makespan by taking into account job-dependent OC. We consider two situations. In the first situation, where the failure rate of a machine under a fixed OC is constant, a hybrid processing time model is proposed to obtain the optimal job sequence based on the Johnson's law. For the second situation, where the failure rate of a machine is time-varying, the job sequence and PM plan are jointly optimized. An enumeration method is adopted to find the optimal job sequence and PM plan for a small-scale problem, and a genetic algorithm-based method is proposed to solve a large-scale problem. Numerical examples are provided to demonstrate the necessity of considering the effect of job-dependent OC and the effectiveness of the proposed method in handing such joint decision-making problems in manufacturing systems.     

A distributed shifting bottleneck heuristic for complex job shops

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities are typical examples for manufacturing systems with these characteristics. The used performance measure is total weighted tardiness (TWT). We suggest a two-layer hierarchical approach in order to decompose the overall scheduling problem. The upper (or top) layer works on an aggregated model. Based on appropriately aggregated routes it determines start dates and planned due dates for the jobs within each single work area, where a work area is defined as a set of parallel machine groups. The lower (or base) layer uses the start dates and planned due dates in order to apply shifting bottleneck heuristic type solution approaches for the jobs in each single work area. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the heuristic. It turns out that the suggested approach outperforms a pure First In First Out (FIFO) dispatching scheme and provides a similar solution quality as the original modified shifting bottleneck heuristic.     

A grammatical optimization approach for integrated process planning and scheduling

Rapid developments in computerized manufacturing environments and increasing overlapping in the capability of manufacturing resources provoked integration of many manufacturing functions including process planning scheduling. Several approaches have been developed in the literature in order to integrate process planning and scheduling. In this paper a novel approach which makes use of grammatical representation of generic process plans is used within a multiple objective tabu search framework in order to integrate process planning and scheduling effectively. Detailed explanations along with an example problem are presented in the paper. Proposed approach is tested on literature problems and also hypothetically generated flexible job shop scheduling problems with alternative process plans to analyze its performance and efficiency.     

Ant colony optimization for multi-objective flow shop scheduling problem

Flow shop scheduling problem consists of scheduling given jobs with same order at all machines. The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, multi-objective approach for scheduling to reduce the total scheduling cost is important. Hence, in this study, we consider the flow shop scheduling problem with multi-objectives of makespan, total flow time and total machine idle time. Ant colony optimization (ACO) algorithm is proposed to solve this problem which is known as NP-hard type. The proposed algorithm is compared with solution performance obtained by the existing multi-objective heuristics. As a result, computational results show that proposed algorithm is more effective and better than other methods compared.     

考虑工件移动时间的柔性作业车间调度问题研究

分析生产车间的实际生产状况,建立了考虑工件移动时间的柔性作业车间调度问题模型,该模型考虑了以往柔性作业车间调度问题模型所没有考虑的工件在加工机器间的移动时间,使柔性作业车间调度问题更贴近实际生产,让调度理论更具现实性。通过对已有的改进遗传算法的遗传操作进行重构,设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。最后对实际案例进行求解,得到调度甘特图和析取图,通过对甘特图和析取图的分析验证了所建考虑工件移动时间的柔性作业车间调度问题模型的可行性和有效性。     

An improved bat optimization algorithm to solve the tasks scheduling problem in open shop

Neural Computing and Applications - The open shop scheduling problem involves a set of activities that should be run on a limited set of machines. The purpose of scheduling open shops problem is to...     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

Job-shop scheduling in a body shop

We study a generalized job-shop problem called the body shop scheduling problem (BSSP). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. BSSP corresponds to a job-shop problem where the operations of a job have to follow alternating routes on the machines, certain operations of different jobs are not allowed to be processed at the same time and after processing an operation of a certain job a machine might be unavailable for a given time for operations of other jobs. As main results we will show that for three jobs and four machines the special case where only one machine is used by more than one job is already $\mathcal NP $ -hard. This also implies that the single machine scheduling problem that asks for a makespan minimal schedule of three chains of operations with delays between the operations of a chain is $\mathcal NP $ -hard. On the positive side, we present a polynomial algorithm for the two job case and a pseudo-polynomial algorithm together with an FPTAS  for an arbitrary but constant number of jobs. Hence for a constant number of jobs we fully settle the complexity status of the problem.