具有柔性加工路径的作业车间批量调度优化研究

古典作业车间调度问题已经被研究了几十年并证明为 NP- hard问题。柔性作业车间调度是古典作业车间调度问题的扩展 ,它允许工序可以由一个机床集合中的多台机床完成加工 ,调度的目的是将工序分配给各机床 ,并对各机床上的工序进行排序以使完成所有工序的时间最小化。本文采用遗传算法进行柔性作业车间调度研究 ,针对柔性作业车间问题提出了一种新颖直观的基因编码方法以适用于批量调度 ,并分析了几种批量调度方案 ,最后给出了这些调度的仿真结果 ,证明单件最佳调度不适合扩展成批量最佳调度     

批量生产柔性作业车间优化调度研究

在批量生产柔性作业车间调度问题中,不但要考虑路径选取和加工排序两个子问题,而且工件还可被分割为多个子批量,不同子批可选择不同工艺路线。该问题是对传统柔性作业车间调度问题(FJSP)的扩充,它更接近于实际生产调度问题。针对问题的特点,提出了一种基于遗传算法的柔性分批调度算法。在算法中,提出了一种基于"游标"的柔性批量分割方法,并采用一种批量分割与加工工序相融合的染色体编码方法。该算法不但可根据机床负荷将工件分割成具有柔性批量的多个子批,而且可使子批工艺路线选取及加工排序同时得到优化。通过实例仿真,对算法性能进行分析和评价,结果表明了算法的有效性和可行性。     

可变机器约束的模糊作业车间调度问题研究

在车间实际加工中,工件的加工时间和交货期是一个模糊数,而且工件的某道工序有多台机器可供选择。针对这类作业的车间调度,提出了以极大化最小客户满意度为指标的可变机器约束的模糊作业车间调度模型,并给出了算法设计。应用遗传算法在适应度函数处理中引入模糊数处理方法,解决作业车间模糊调度问题,实现调度优化。仿真实验结果表明了该调度方法的有效性,为可变机器约束的模糊作业车间调度提供了一种实现途径。     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

ACO-based multi-objective scheduling of parallel batch processing machines with advanced process control constraints

This research was motivated by a scheduling problem in the dry strip operations of a semiconductor wafer fabrication facility. The machines were modeled as parallel batch processing machines with incompatible job families and dynamic job arrivals, and constraints on the sequence-dependent setup time and the qual-run requirements of advanced process control. The optimization had multiple objectives, the total weighted tardiness (TWT) and makespan, to consider simultaneously. Since the problem is NP-hard, we used an Ant Colony Optimization (ACO) algorithm to achieve a satisfactory solution in a reasonable computation time. A variety of simulation experiments were run to choose ACO parameter values and to demonstrate the performance of the proposed method. The simulation results showed that the proposed ACO algorithm is superior to the common Apparent Tardiness Cost-Batched Apparent Tardiness Cost rule for minimizing the TWT and makespan. The arrival time distribution and the number of jobs strongly affected the ACO algorithm’s performance.     

Lot splitting scheduling procedure for makespan reduction and machine capacity increase in a hybrid flow shop with batch production

The general definition of the hybrid flow shop (HFS) environment is a set of S?≥?2 production stages where at least one of these stages includes more than one machine, which can process one job at a time. A job can be defined as several operations to be performed by none, one, or more machines at each stage. Usually, these jobs are completed in some sequence between the different production stages, and in the case of setup activities, products are grouped in batches with buffers of work in progress between different production stages. Today, flexible production systems permit in some instances to relax job precedence constrains with alternative process cycles and to group together different batches of similar products in order to reduce setup activity incidence. On the other hand, the availability of multiple parallel machines in a single production stage makes it possible to split the lot size between different resources. This paper aims to solve the HFS scheduling problem in a flexible multistage batch production system, offering a heuristic procedure, to minimize the production makespan and increase the productive capacity utilization using a batch aggregation/splitting strategy while introducing the “workload leveling function” concept. The results are compared with other important scheduling rules widely accepted in the industry and made part of an industrial application. The company used as a test sample is an Italian rotor shaft manufacturer. The final result is illustrated to validate the proposed heuristics.     

Lot streaming in a two-machine mixed shop

Most classical scheduling models overlook the fact that products are often produced in job lots and assume that job lots are indivisible single entities, although an entire job lot consists of many identical items. However, splitting an entire lot (process batch) into sublots (transfer batches) to be moved to downstream machines allows the overlapping of different operations on the same product while work needs to be completed on the upstream machine. This approach is known as lot streaming in scheduling theory. In this study, the lot streaming problem of multiple jobs in a two-machine mixed shop where there are two different job types as flow shop and open shop is addressed so as to minimize the makespan. The optimal solution method is developed for the mixed shop scheduling problem in which lot streaming can improve the makespan.     

基于混合差分进化算法的并行机批处理调度问题研究

考虑到实际生产中产品多、批量小的特点,建立了一种带工艺约束的并行机批处理调度优化模型。为解决调度中的分批问题,提出了一种新的基于产品需求量的批量划分方案及批量染色体编码方式,采用两级差分进化算法来解决批量划分和批次调度问题;针对标准差分进化算法收敛速度慢、易出现早熟现象等问题,引入动态随机搜索和随机变异的局部搜索策略,以增强标准差分进化算法的局部搜索能力。测试算例及调度实例的仿真结果表明,该算法能有效地提高算法收敛速度,平衡其全局搜索和局部探索能力。     

NEW NONSTANDARD JOB SHOP SCHEDULING ALGORITHM

Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.     

A mixed integer programming formulation for scheduling of virtual manufacturing cells (VMCs)

We present a multi-objective mixed integer programming formulation for job scheduling in virtual manufacturing cells (VMCs). In a VMC, machines are dedicated to a part family 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. The two scheduling objectives are makespan minimization and minimizing total traveling distance. Since batch splitting is permitted in the system, scheduling decisions must tell us the (a) assignment of jobs to the machines, (b) the job starting time at each machine, and (c) the part quantity processed on different machines due to batch splitting. Under these decision variables, the objective function is to minimize the sum of the makespan and total traveling distance/cost. Illustrative examples are given to demonstrate the implementation of the model.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines

This paper considers a flow shop with two batch processing machines. The processing times of the job and their sizes are given. The batch processing machines can process multiple jobs simultaneously in a batch as long as the total size of all the jobs in a batch does not exceed its capacity. When the jobs are grouped into batches, the processing time of the batch is defined by the longest processing job in the batch. Batch processing machines are expensive and a bottleneck. Consequently, the objective is to minimize the makespan (or maximize the machine utilization). The scheduling problem under study is NP-hard, hence, a genetic algorithm (GA) is proposed. The effectiveness (in terms of solution quality and run time) of the GA approach is compared with a simulated annealing approach, a heuristic, and a commercial solver which was used to solve a mixed-integer formulation of the problem. Experimental study indicates that the GA approach outperforms the other approaches by reporting better solution.     

Discrete artificial bee colony algorithm for lot-streaming flowshop with total flowtime minimization

Unlike a traditional flowshop problem where a job is assumed to be indivisible, in the lot-streaming flowshop problem, a job is allowed to overlap its operations between successive machines by splitting it into a number of smaller sub-lots and moving the completed portion of the sub-lots to downstream machine. In this way, the production is accelerated. This paper presents a discrete artificial bee colony (DABC) algorithm for a lot-streaming flowshop scheduling problem with total flowtime criterion. Unlike the basic ABC algorithm, the proposed DABC algorithm represents a solution as a discrete job permutation. An efficient initialization scheme based on the extended Nawaz-Enscore-Ham heuristic is utilized to produce an initial population with a certain level of quality and diversity. Employed and onlooker bees generate new solutions in their neighborhood, whereas scout bees generate new solutions by performing insert operator and swap operator to the best solution found so far. Moreover, a simple but effective local search is embedded in the algorithm to enhance local exploitation capability. A comparative experiment is carried out with the existing discrete particle swarm optimization, hybrid genetic algorithm, threshold accepting, simulated annealing and ant colony optimization algorithms based on a total of 160 randomly generated instances. The experimental results show that the proposed DABC algorithm is quite effective for the lot-streaming flowshop with total flowtime criterion in terms of searching quality, robustness and effectiveness. This research provides the references to the optimization research on lot-streaming flowshop.     

柔性作业车间多品种小批量调度算法研究

提出一种多目标混合遗传算法(MIGA),采用集成法同时解决柔性作业车间调度的两个子问题:机器分配问题和工序调度问题。MIGA在标准遗传算法的基础上采用随机权重法解决多目标问题,引入精英保留策略加速算法的收敛,集成小生境技术提高种群的多样性,基于扩展工序编码,按Makespan和安装准备成本最优对调度批分别解码。最后,用标准算例进行了算法验证,证明MIGA可以有效解决柔性作业车间多品种小批量调度问题。     

基于免疫算法的并行机间歇过程模糊生产调度

研究了一类具有顺序无关模糊产品切换时间和成本以及模糊单位加工时间和成本的并行机间歇过程调度问题,目的是确定每种产品在每个设备上处理的批次数目、批量以及批次顺序,优化目标为最小化总完成时间和最小化总生产成本。根据任意设备上同种产品的所有批次均顺序处理的性质,建立了问题的模糊运输模型。利用加权和方法将多目标函数转化为单目标函数,并使用基于积分值的方法对模糊数进行排序。提出了基于排列边集编码的免疫算法,通过求解不同规模的问题实例证明,免疫算法不仅能获得比遗传算法和免疫遗传算法更好的解,而且比免疫遗传算法更高效,同时具有良好的动态性能。     

批量生产作业车间的双资源多目标调度问题研究

对于批量生产调度问题,根据批次判定公式确定每种工件能划分的批数及每批的工件数,然后把每个子批当作一个新的工件进行调度。采用遗传算法和禁忌搜索算法相结合的混合优化调度算法,用于解决同时考虑设备和工人的双资源问题,以及综合考虑生产周期、工件总延误时间、设备闲置时间和工人闲置时间的多目标综合优化问题。其中采用多目标决策理论用于确定遗传算法中的目标函数,以及由非劣解集合获得较优解。调度算例表明本研究能获得很好的调度效果。     

服务型制造车间关键任务调度的Stackelberg博弈研究

针对服务型制造车间关键任务调度问题,提出了两层次嵌套的Stackelberg博弈调度模型。该博弈模型由Stackelberg子博弈与非合作静态子博弈构成。其中Stackelberg子博弈模型用于解决关键任务与非关键任务的之间的调度决策问题,非合作静态子博弈模型则用于实现非关键任务之间的调度决策。在该博弈调度模型中,将关键任务映射为领导者,将其余非关键任务映射为追随者,将与各任务包含的工序集所对应的可选加工设备映射为可行方案集,将各任务的综合成本指标映射为收益函数。为实现对模型的Stackelberg均衡点的有效求解,设计了基于爬山搜索的混合自适应遗传算法。算例仿真结果验证了所提出的模型与解算方法的正确性。     

考虑批量和辅助时间等生产工况的智能调度方法

根据车间调度实际要求,综合考虑批量、毛坯到达时间和辅助时间等生产工况,研究复杂生产调度问题。给出了此问题的模型及求解此问题的生物免疫算法模型,并介绍了基于生物免疫机理的智能调度方法实现过程中的关键技术,包括抗体编码设计、工件起始加工时间的计算准则和优化方法、交叉和变异操作等。对考虑辅助时间、批量等多工况问题的测试结果表明,所提出的综合考虑批量和辅助时间等生产工况的智能调度方法是有效的, 且在调度过程中考虑批量是必要的。     

A study of the flexible job shop scheduling problem with parallel machines and reentrant process

This paper develops a scheduling algorithm for the job shop scheduling problem with parallel machines and reentrant process. This algorithm includes two major modules: the machine selection module (MSM) and the operation scheduling module (OSM). An order has several jobs and each job has several operations in a hierarchical structure. The MSM helps an operation to select one of the parallel machines to process it. The OSM is then used to schedule the sequences and the timing of all operations assigned to each machine. A real-life weapons production factory is used as a case study to evaluate the performance of the proposed algorithm. Due to the high penalty of delays in military orders, the on-time delivery rate is the most important performance measure and then makespan is the next most important measure. Well-known performance measures in the scheduling literature, such as maximum lateness and average tardiness, are also evaluated. The simulation results demonstrate that the MSM and OSM using the combination of earliest due date (EDD), the operations’ lowest level code (LLC) of the bill of materials (BOM), and the longest processing time (LPT) outperforms the other scheduling methods.