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

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

考虑准备时间和工件分批的柔性作业车间调度

针对柔性作业车间调度受生产准备时间和工件批量影响的问题,构建了考虑准备时间和工件分批的柔性作业车间调度模型.根据工件批量加工中等量分批方法柔性不足的特点,采用柔性分批方法对工件进行批量划分.提出一种改进的遗传算法,以最小化最大完工时间为优化目标,采用双层编码的方式对模型求解,确定各工件的分批方案和子批工序调度排序方案.通过分析柔性调度案例,验证了该算法的有效性,能够更好地满足实际车间生产要求.     

基于遗传算法的多资源作业车间智能动态优化调度

提出一种基于遗传算法的调度算法，用于解决多资源制约(机床、工人和机器人)条件下作业车间的动态优化调度。为了表达加工工件的批量，提出了一种新的染色体基因型，基因型的长度随加工环境的变化而变化。研究的动态环境包括：加工工件连续不断地到来；机床设备突然损坏；损坏的机床被修复；工件的预定订货时间被提前；有新类型的工件要求被加工等等。采用一种基于周期和事件驱动的滚动窗口调度，以适应连续加工过程中的环境变化。调度算法中采用权重可变的双目标评价函数来优化调度结果。仿真结果表明该算法是可行的，与传统的静态优化调度相比，其优越性是明显的。     

作业车间多工艺路线批量作业计划优化

提出一种基于遗传算法的作业计划算法,用于解决作业车间的中小批量多工艺加工作业计划的优化问题。在作业计划算法中,提出了一种将工件的子批数量和加工工序包容在一起的染色体编码方法,使得子批数量的确定和子批加工顺序的安排能够被同时优化。以生产周期为目标优化作业计划,将遗传算法和分派规则相结合,通过交叉、变异等遗传操作,得到目标的最优或次优解。最后对算法进行了仿真研究,并给出了算法运行结果,仿真结果表明该算法是可行的。     

柔性作业车间中基于工序分批的调度问题与求解

考虑到柔性作业车间分批调度中不同工序具有各自合适批量大小,提出了基于工序分批调度的概念,建立了以关键路径工序为中心的分批调度模型。该模型动态更新可加工工序子批集,同时更新可选加工机器,及时调整加工路线,为不同工序安排大小合适的批量,以达到优化完工时间、有效降低总加工批次的目的。实验结果表明,相比基于工件分批的调度,该模型在优化最长完工时间、提高机器利用率的同时,大幅减少了总加工批次数量(42%),降低了车间调度管理的复杂度。     

考虑动态资源和工件批量约束的柔性车间生产调度

针对实际车间生产调度过程中车间设备资源受上一调度周期剩余任务影响、工件批量和加工路径柔性等问题,构建考虑设备动态负荷和工件批量约束的柔性车间生产调度模型。提出双层嵌套式遗传算法:外层遗传算法确定工件批量划分和各子批零件的工艺路径,并设计一种基于设备优选法的解码算子来确定个体对应的批量划分中各子批零件的工艺路径;内层遗传算法确定外层遗传算法个体所对应的工件分批和加工路径约束下的调度方案,调度方案的完工时间和超出交货期时间将反馈到外层遗传算法中,用于综合评估当前分批和加工路径方案的性能,实现综合优化。最后在柔性调度标准案例10×10案例基础上增加批量、交货期、设备资源等约束,对所提模型和算法进行测试,结果表明所提算法在对工件进行合理分批和工艺路径确定的同时,能够优化调度结果,满足产品交货期和设备资源约束。     

考虑机床调整和工件批量加工的车间调度问题模型研究

针对工件品种多、工序复杂,机床在批量同种工序首件加工前需进行调整等问题,研究出一种以机床总能耗最小和工件的最大完工时间最小为优化目标的生产调度模型。使用遗传算法对提出的模型进行快速精确求解。运用Matlab软件平台对实际案例进行仿真,将新旧模型的计算结果进行对比,结果表明建立的模型是有效和实用的,能更有效地指导实际生产。     

多目标柔性作业车间分批优化调度

为解决多目标柔性作业车间分批调度问题,提出了一种基于粒子群算法的多目标柔性分批调度算法。提出了一种基于游标的柔性批量分割方法,并采用一种批量分割与加工工序相融合的粒子编码方法,使得该算法不但可根据机床负荷将工件分割成具有柔性批量的多个子批,而且可使子批工艺路线选取及加工排序同时得到优化。算法引入了决策者的偏好信息,用于引导算法的搜索方向,使搜索结果集中于决策者感兴趣的Pareto边沿,避免了决策者在众多非劣解中做出困难选择。通过实例仿真,对算法性能进行了比较分析和评价,结果表明了算法的有效性和可行性。最后,从生产实际出发给出了算例,证明了算法的有效性和对生产实践的指导作用。     

柔性作业车间批量划分与并行调度优化

针对柔性作业车间分批调度中因批次数量划分的随机性,导致最优分批方案存在搜索空间大、效率低的问题,提出试探法,使分批具有方向性、搜索空间可预测,从而得到合适的批量划分。进而提出相同工件同批工序间、不同工序间可并行的车间调度算法,与传统的批量调度结果相比,该算法可缩短生产周期、提高车间生产效率、减少批次数量、降低车间管理复杂度。采用上述方法对批次数量进行划分并使用并行算法对划分后的工序进行调度,实验结果表明,该方法在快速找到合适分批方案的同时优化了调度结果。     

多工艺路线的作业车间模糊调度优化

对具有模糊加工时间和模糊交货期的多工艺路线的作业车间调度问题进行了研究；以最大化平均满意度为调度目标，建立了作业车间模糊调度的数学模型，提出了一种基于遗传算法的全局优化的调度算法；设计了包含工序及其加工机床信息的染色体编码，对染色体的解码方法、交叉方法和变异方法进行了研究。仿真结果表明，该算法是可行的，与其他同类研究相比，有一定的优越性。     

Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing

In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.     

Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates

This study considers the scheduling problem observed in the burn-in operation of semiconductor final testing, where jobs are associated with release times, due dates, processing times, sizes, and non-agreeable release times and due dates. The burn-in oven is modeled as a batch-processing machine which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity and the processing time of a batch is equal to the longest time among all the jobs in the batch. Due to the importance of on-time delivery in semiconductor manufacturing, the objective measure of this problem is to minimize total weighted tardiness. We have formulated the scheduling problem into an integer linear programming model and empirically show its computational intractability. Due to the computational intractability, we propose a few simple greedy heuristic algorithms and meta-heuristic algorithm, simulated annealing (SA). A series of computational experiments are conducted to evaluate the performance of the proposed heuristic algorithms in comparison with exact solution on various small-size problem instances and in comparison with estimated optimal solution on various real-life large size problem instances. The computational results show that the SA algorithm, with initial solution obtained using our own proposed greedy heuristic algorithm, consistently finds a robust solution in a reasonable amount of computation time.     

成批生产计划调度的集成建模与优化

针对多品种批量生产类型,建立了调度约束的生产计划与调度集成优化模型。模型的目标函数是使总调整费用、库存费用及生产费用之和最小,约束函数包括库存平衡约束和生产能力约束,同时考虑了调度约束,即工序顺序约束和工件在单机上的加工能力约束,保证了计划可行性。该模型为两层混合整数规划模型,对其求解综合运用了遗传算法和启发式规则,提出了混合启发式求解算法。最后,针对某机床厂多品种批量生产类型车间进行了实例应用,对车间零件月份作业计划进行分解,得到各工段单元零件周作业计划,确定了零件各周生产批量与投产顺序。     

Sequencing heuristic for scheduling jobs with dependent setups in a manufacturing system

In this paper we discuss a single-machine scheduling problem with machine maintenance. In many production systems, the sequence-dependent setup time of a job cannot be ignored when a switch between two different jobs occurs. In our research, we develop a heuristic to minimize the completion time, or equivalently the total setup time subject to maintenance and due dates. The heuristic consists of three procedures: the initialization procedure, the Stinson heuristic procedure and the iterative procedure. Computational performance of the heuristic is evaluated by comparing its solution with the solution of the branch-and-bound algorithm. The performance of the heuristic on various sizes problems is provided.     

Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints

We consider the unrelated parallel-machine scheduling problem with sequence- and machine-dependent setup times and due-date constraints. There are N jobs, each having a due date and requiring a single operation on one of the M machines. A setup is required if there is a switch from processing one type of job to another. Due to the characteristics of machines, the processing time depends upon the job and machine on which the job is processed, and the setup time is sequence and machine dependent. In addition, certain jobs have strict due-date constraints. An effective heuristic based on a modified apparent-tardiness-cost-with-setup procedure, the simulated annealing method, and designed improvement procedures is proposed to minimize the total tardiness of this scheduling problem. Computational characteristics of the proposed heuristic are evaluated through an extensive experiment using a newly created data set. Computational results show that the proposed heuristic is able to effectively improve the initial solutions, obtained by a modified apparent-tardiness-cost-with-setup procedure, and obtains better results than a random descent heuristic.     

单机成组调度问题的约束满足建模与求解方法

为适应多品种小批量生产需求,企业普遍采用基于成组技术的混流生产,由此产生的成组调度需要平衡安装时间减少与满足交期之间的冲突关系。在分析安装时间是否依赖工件组排序、工件组能否分割加工等成组特征的基础上,以最小化加权流程时间与加权拖期为目标,构建了单机成组调度问题的约束满足模型,提出了以变量排序启发式搜索和前向约束传播相结合的求解方法。典型生产数据的实证分析表明,所提出的方法建模能力强,解的适应性好。     

Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints

The unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times in the presence of due date constraints represents an important but relatively less-studied scheduling problem in the literature. In this study, a simple iterated greedy (IG) heuristic is presented to minimize the total tardiness of this scheduling problem. The effectiveness and efficiency of the proposed IG heuristic are compared with existing algorithms on a benchmark problem dataset used in earlier studies. Extensive computational results indicate that the proposed IG heuristic is capable of obtaining significantly better solutions than the state-of-the-art algorithms on the same benchmark problem dataset with similar computational resources.     

A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of jobs that visit a set of machines in the same order. The FSP is NP-hard, which means that there is no efficient algorithm to reach the optimal solution of the problem. To minimize the make-span of large permutation flow-shop scheduling problems in which there are sequence-dependent setup times on each machine, this paper develops one novel hybrid genetic algorithms (HGA). Proposed HGA apply a modified approach to generate the population of initial chromosomes and also use an improved heuristic called the iterated swap procedure to improve them. Also the author uses three genetic operators to make good new offspring. The results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of the solutions.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system.The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence.A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

两机零等待流水车间调度问题的启发式算法

为实现两机零等待流水车间调度问题的总流程时间最小化,结合问题的结构信息提出了一种快速求解近优解的启发式算法。在该类问题中,工件在每台机器上的操作包括调整、加工和移除3部分,且调整和移除时间都与工件的加工时间相互分离。首先分析了该类问题的优化性质,结合优化性质进而构造出求解算法。在中小规模和大规模问题上,将启发式算法的结果分别与最优解和最优解的下界值进行了比较。大量数值计算实验表明了该算法的有效性和解决大规模实际问题的潜力。