A holonic approach to flexible flow shop scheduling under stochastic processing times

Flexible flow shop scheduling problems are NP-hard and tend to become more complex when stochastic uncertainties are taken into consideration. This paper presents a novel decomposition-based holonic approach (DBHA) for minimising the makespan of a flexible flow shop (FFS) with stochastic processing times. The proposed DBHA employs autonomous and cooperative holons to construct solutions. When jobs are released to an FFS, the machines of the FFS are firstly grouped by a neighbouring K-means clustering algorithm into an appropriate number of cluster holons, based on their stochastic nature. A scheduling policy, determined by the back propagation networks (BPNs), is then assigned to each cluster holon for schedule generation. For cluster holons of a low stochastic nature, the Genetic Algorithm Control (GAC) is adopted to generate local schedules in a centralised manner; on the other hand, for cluster holons of a high stochastic nature, the Shortest Processing Time Based Contract Net Protocol (SPT-CNP) is applied to conduct negotiations for scheduling in a decentralised manner. The combination of these two scheduling policies enables the DBHA to achieve globally good solutions, with considerable adaptability in dynamic environments. Computation results indicate that the DBHA outperforms either GAC or SPT-CNP alone for FFS scheduling with stochastic processing times.     

Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems

This article addresses the problem of hybrid flexible flow line where some constraints are considered to alleviate the chasm between the real-world industries scheduling and the production scheduling theories. Sequence-dependent setup times, machine release date and time lags are three constraints deemed to project the circumstances commonly found in real-world industries. To tackle the complexity of the problem at hand, we propose an approach base on genetic algorithm (GA). However, the performance of most evolutionary algorithms is significantly impressed by the values determined for the miscellaneous parameters which these algorithms possess. Hence, response surface methodology is applied to set the parameters of GA and to estimate the proper values of GA parameters in continually intervals. Finally, problems of various sizes are utilized to test the performance of the proposed algorithm and to compare it with some existing heuristic in the literature such as SPT, LPT and NEH.     

Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in permutation flow shop scheduling problems. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on a greedy randomized constructive heuristic, a genetic algorithm (GA) for solution evolution, and a variable neighbourhood search (VNS) to improve the population. The hybridization of a GA with VNS, combining the advantages of these two individual components, is the key innovative aspect of the approach. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high-quality solutions in short computational times. Furthermore, it requires very few user-defined parameters, rendering it applicable to real-life flow shop scheduling problems.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性 函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费 用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用 Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则 Flowshop问题可以转化为单机问题.     

Simulation optimization approach for hybrid flow shop scheduling problem in semiconductor back-end manufacturing

This study presents a simulation optimization approach for a hybrid flow shop scheduling problem in a real-world semiconductor back-end assembly facility. The complexity of the problem is determined based on demand and supply characteristics. Demand varies with orders characterized by different quantities, product types, and release times. Supply varies with the number of flexible manufacturing routes but is constrained in a multi-line/multi-stage production system that contains certain types and numbers of identical and unrelated parallel machines. An order is typically split into separate jobs for parallel processing and subsequently merged for completion to reduce flow time. Split jobs that apply the same qualified machine type per order are compiled for quality and traceability. The objective is to achieve the feasible minimal flow time by determining the optimal assignment of the production line and machine type at each stage for each order. A simulation optimization approach is adopted due to the complex and stochastic nature of the problem. The approach includes a simulation model for performance evaluation, an optimization strategy with application of a genetic algorithm, and an acceleration technique via an optimal computing budget allocation. Furthermore, scenario analyses of the different levels of demand, product mix, and lot sizing are performed to reveal the advantage of simulation. This study demonstrates the value of the simulation optimization approach for practical applications and provides directions for future research on the stochastic hybrid flow shop scheduling problem.     

Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, maximum lateness, maximum cost and number of late jobs. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.     

A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem

In this paper, a novel competitive co-evolutionary quantum genetic algorithm (CCQGA) is proposed for a stochastic job shop scheduling problem (SJSSP) with the objective to minimize the expected value of makespan. Three new strategies named as competitive hunter, cooperative surviving and the big fish eating small fish are developed in population growth process. Based on improved co-evolution idea of multi-population and concepts of quantum theory, this algorithm could not only adjust population size dynamically to increase the diversity of genes and avoid premature convergence, but also accelerate the convergence speed with Q-bit representation and quantum rotation gate. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by CCQGA. The experiment results achieved by CCQGA are compared with quantum-inspired genetic algorithm (QGA) and standard genetic algorithm (GA), which shows that CCQGA has better feasibility and effectiveness.     

Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times

Due date assignment combined with shop floor scheduling has attracted enormous amount of research, in recent years. In many make-to-order situations, the processing times are not known exactly in advance. Further, machine rates are not constant at different times. We assume the case where the machine rate is low at the beginning of the scheduling horizon. However, it can be brought back to normal rate by performing a maintenance activity. The problem includes assigning due-dates and scheduling the jobs and maintenance activity on a single machine where the processing times are stochastic. The objective is minimizing the total cost of lengths of quoted due-dates and expected deviations of completion times from declared due-dates. The optimal solutions of medium-sized problems are found by solving some nonlinear programming models. For larger problems, robust metaheuristics are developed and their performances are statistically analyzed.     

Reliability evaluation of a multistate flexible flow shop with stochastic capacity for multiple types of jobs

A flexible flow shop (FFS) is a general manufacturing system that has been studied by numerous researchers. Owing to maintenance, partial failure, the possibility of failure, unexpected situations, etc., the number of functioning machines in a stage should be represented by multiple levels. It is appropriate to regard the capacity in each stage (i.e., the number of machines in a stage) as stochastic. Unlike the previous research, which dealt with the FFS problems under the assumption of the fixed capacity, this paper extends the deterministic capacity to the stochastic case in every stage. The FFS with stochastic capacity is modeled as a multistate flexible flow shop network (MFFSN), where each edge denotes a stage with stochastic capacity and each node denotes a buffer. The addressed problem is to evaluate network reliability, the probability that the MFFSN can complete a customer's order composed of multiple types of jobs within a time threshold. An efficient algorithm integrating a systematic branch-and-bound approach is proposed to obtain the lower boundary vectors, in terms of a pair of capacity vectors generated from two estimated demand vectors. Two practical cases, a tile production system and an apparel manufacturing system, are presented to demonstrate the proposed algorithm and to discuss the changes in network reliability within different time thresholds, respectively.     

基于机床超低待机状态的流水车间能耗调度

为降低流水车间能源消耗,引入一种数控机床的超低待机状态,相比于将数控机床待机状态切换为停机状态的节能研究,可在不停机情况下降低数控机床加工间隔状态的功率,避免数控机床频繁启停.针对流水车间加工状态、待机状态及超低待机状态三元调度问题,提出基于工序平移的混合遗传算法,分别定义了不同的工序邻域移动操作,实现数控机床待机状态向超低待机状态和停机状态的转化,形成主动节能调度策略,提升遗传算法求解考虑超低待机状态的流水车间调度问题的优化能力.实验研究表明,启用超低待机状态能够降低流水车间10%以上的能耗,且基于工序平移的混合遗传算法求解考虑超低待机状态的流水车间调度问题性能优于遗传算法.     

Fuzzy branch-and-bound algorithm for flow shop scheduling

Scheduling is the allocation of resources over time to perform a collection of task. It is an important subject of production and operations management area. For most of scheduling problems made so far, the processing times of each job on each machine and due dates have been assigned as a real number. However in the real world, information is often ambiguous or imprecise. In this paper fuzzy concept are applied to the flow shop scheduling problems. The branch-and-bound algorithm of Ignall and Schrage was modified and rewritten for three-machine flow shop problems with fuzzy processing time. Fuzzy arithmetic on fuzzy numbers is used to determine the minimum completion time (C _max). Proposed algorithm gets a scheduling result with a membership function for the final completion time. With this membership function determined, a wider point of view is provided for the manager about the optimal schedule.     

A note on scheduling problems with learning effect and deteriorating jobs

In this note, we consider the machine scheduling problems with the effects of deterioration and learning. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The scheduling objectives are makespan (weighted) sum of completion times and maximum lateness. It is shown that even with the introduction of deterioration and learning effect to job processing times, several single machine problems and several flow shop problems remain polynomially solvable, respectively.     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling

This paper proposes a method for solving stochastic job‐shop scheduling problems using a hybrid of a genetic algorithm in uncertain environments and the Monte Carlo method. First, the genetic algorithm in uncertain environments is applied to stochastic job‐shop scheduling problems where the processing times are treated as stochastic variables. The Roulette strategy is adopted for selecting the optimum solution having the minimum expected value for makespan. Applying crossover based on Giffler and Thompson's algorithm results in two offspring inheriting the ancestor's characteristics as the operation completion times averaged up to the parent's generation. Individuals having very high frequency through all generations are selected as the good solutions. Second, the Monte Carlo method is effectively used for finding out the approximately optimum solution among these good solutions.     

A genetic algorithm based heuristic for scheduling of virtual manufacturing cells (VMCs)

We present a genetic algorithm (GA) based heuristic approach for job scheduling in virtual manufacturing cells (VMCs). In a VMC, machines are dedicated to a part as in a regular cell, but machines are not physically relocated in a contiguous area. Cell configurations are therefore temporary, and assignments are made to optimize the scheduling objective under changing demand conditions. We consider the case where there are multiple jobs with different processing routes. There are multiple machine types with several identical machines in each type and are located in different locations in the shop floor. Scheduling objective is weighted makespan and total traveling distance minimization. The scheduling decisions are the (i) assignment of jobs to the machines, and (ii) the job start time at each machine. To evaluate the effectiveness of the GA heuristic we compare it with a mixed integer programming (MIP) solution. This is done on a wide range of benchmark problem. Computational results show that GA is promising in finding good solutions in very shorter times and can be substituted in the place of MIP model.     

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.     

Genetic algorithms applied to the continuous flow shop problem

This research develops an approach for applying Genetic Algorithms (GA) to scheduling problems. We generate a GA based heuristic for continuous flow shop problems with total flow time as the criterion. The effects of several crucial factors of GA on the performance of the heuristic for the problem are explored in detail. The computational experience of heuristic provides several observations of the application of GA, and strongly supports that the applications of GA are problem specific. The computational experience also shows that GA can be good techniques for scheduling problems.     

Two-machine flow shop scheduling integrated with preventive maintenance planning

This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.