多层级装配作业车间分批调度算法设计与分析

多层级装配作业车间调度是一类包含加工与装配的双阶段调度问题，装配产品具有不同的树状结构，且各层级的装配工序需要直属零部件完工方可执行。分批调度可以提高车间生产流动性，故而被运用在作业车间调度等领域。装配作业车间分批调度需要解决关联零部件及其下属子批的进度协同性问题，为此建立了多层级装配作业车间的分批优化调度模型，以最小化拖期成本与库存持有成本为优化目标。出于求解效率考虑，构建基于遗传算法与优先分派规则的混合求解算法以应对批量划分与排序两个子问题。最后，设计仿真实验验证分批调度算法的有效性，并分析评估在8种作业分派规则、3类分批策略下混合算法对于差异化产品结构的适应性。通过分析实验结果发现，等量分批策略可以在给定条件下有效提升混合算法的调度性能。     

装配作业车间分批调度问题的算法对比

建立最小化makespan的装配作业车间分批调度模型,利用遗传算法构建基于整体集成优化策略、分层迭代优化策略和双层进化策略的求解算法。它们的区别在于处理批量划分问题和子批调度问题的联合优化机制不同。最后通过仿真实验对比了几类算法的求解效果和收敛速度,并分析了它们的适应性特点。     

基于公理设计的车间调度算法研究

车间调度问题是典型的NP难题,也是一种完全耦合的复杂系统.基于公理设计思想对车间调度系统进行了解耦设计,给出了相应的解耦思路及解耦矩阵,提出并实现了一种车间调度算法,并对算法的复杂性进行了分析.以实际车间生产调度作为研究对象,针对实际生产中零件紧急程度不一的情况,为待加工零件赋予不同的权值,并优先考虑调度加工工时较长的零件;采用以解耦设计为总目标,在满足约束条件的情况下,尽量优化压缩加工时间.对算法的复杂性进行了分析,该算法属于三次多项式复杂级,较优于一般的算法.通过2个实例计算和对比,验证了本算法的实用性和有效性.     

增强现实环境下的产品装配引导技术

以增强现实环境下引导产品装配为目标,建立了面向增强装配过程的统一信息模型,管理文字、几何和产品装配特征等可视化引导信息。采用基于标志物的视觉跟踪技术实现虚拟零件和视频中真实零件的注册定位,通过建立虚拟和真实装配场景的深度图处理增强装配场景中虚实物体的遮挡关系。利用虚实零件的注册位置把装配引导信息叠加到装配视频场景中。并开发了演示系统,分析和说明了增强现实环境下引导产品进行装配的过程。     

基于广义键的产品可装配性模糊评价方法研究

提出基于广义键的产品可装配性模糊评价方法。采用多重配连接图描述产品中零件之间的多重装配关系，研究了基于模糊装配连接图中的结点和连接连的模糊度来描述和评价产品的可装配性。建立了产品可装配性评价体系；基于产品装配数据和装配知识对产品可装配性进行模糊定量评价，从而指导产品装配设计。     

有模具约束的并行机批量流调度问题研究

大多数调度问题均假设产品以单个或整批的方式进行生产,而实际生产过程中,会把产品分批后再进行生产。但当考虑模具约束时,对如何解决产品分批以及制定合理调度方案的问题,本文以最小化最大完工时间为优化目标,建立了考虑模具约束的并行机批量流调度模型,并提出了一种基于遗传算法和差分算法结合的混合差分遗传算法（DEGA）,实现分批与调度两个问题并行优化。最后通过对算例测试,DEGA算法得到更优的解,证明了该算法的优越性和稳定性。结合实际案例,验证了模型和算法的可行性。     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

柔性制造系统生产中的零件分批算法

根据ＦＭＳ资源、加工任务、零件工艺提出了零件分批算法，该算法在零件交货期的束下，以机床负荷平衡为目标，搜索零件集合，找出最合适的零件组合形成零件加工批。此算法为简化ＦＭＳ的动态调度和提高系统生产率创造了条件。仿真结果表明分批算法是行之有效的。     

具有成组约束的柔性同序加工车间的排序算法

针对轮胎模具的生产调度特点,研究了具有成组约束的两阶段柔性同序加工车间(FF2)的调度问题,建立了目标函数为最小化最大完成时间的调度数学模型,基于Johnson准则提出一种新的启发式算法,并应用企业的实际算例,说明了数学模型和求解方法的可靠性和有效性。     

基于机器视觉的微小型零件精密装配

基于机器视觉的精密装配是实现微小型零件自动组装的重要方法.所研制的基于机器视觉的自动装配系统解决了某小型产品装配中的关键问题,其中包括待装配的零件尺寸相差大、形状和特征多样、表面质量差别较大、需要同时保证组装的位置精度和形位公差等.采用Canny边缘提取、圆的最小二乘拟合、轮廓提取、质心主轴计算、图像拼接等方法实现了待装配零件的识别定位,通过设备坐标系统的转换保证了小型零件的精确装配.实验结果表明装配精度小于40μm.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.     

Integrated scheduling and self-reconfiguration for assembly job shop in knowledgeable manufacturing

The problems of integrated assembly job shop (AJS) scheduling and self-reconfiguration in knowledgeable manufacturing are studied with the objective of minimising the weighted sum of completion cost of products, the earliness penalty of operations and the training cost of workers. In AJS, each workstation consists of a certain number of teams of workers. A product is assumed to have a tree structure consisting of components and subassemblies. The assembly of components, subassemblies and final products are optimised with the capacity of workstations simultaneously. A heuristic algorithm is developed to solve the problem. Dominance relations of operations are derived and applied in the development of the heuristic. A backward insertion search strategy is designed to locally optimise the operation sequence. Once the optimal schedule is acquired, the teams are reconfigured by transferring them from workstations of lower utilisation to those of higher utilisation. Effectiveness of the proposed algorithm is tested by a number of numerical experiments. The results show that the proposed algorithm promises lower total cost and desirable simultaneous self-reconfiguration in accordance with scheduling.     

A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem

This paper presents a study on the two-stage assembly flow shop scheduling problem for minimising the weighed sum of maximum makespan, earliness and lateness. There are m machines at the first stage, each of which produces a component of a job. A single machine at the second stage assembles the m components together to complete the job. A novel model for solving the scheduling problem is built to optimise the maximum makespan, earliness and lateness simultaneously. Two optimal operation sequences of jobs are determined and verified. As the problem is known to be NP-hard, a hybrid variable neighbourhood search – electromagnetism-like mechanism (VNS-EM) algorithm is proposed for its handling. To search beyond local optima for a global one, VNS algorithm is embedded in each iteration of EM, whereby the fine neighbourhood search of optimum individuals can be realised and the solution is thus optimised. Simulation results show that the proposed hybrid VNS-EM algorithm outperforms the EM and VNS algorithms in both average value and standard deviation.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

Integrated modelling and algorithm of material delivery and line-side storage for aircraft moving assembly lines

This paper considers the material supply problem for aircraft moving assembly lines. Distinguished from general automobile assembly lines, multiple parallel jobs are assembled concurrently and durations of assembly jobs are quite long, thus amounts of materials are orderly stored at the line-side space at the same time. In addition, the line-side space should be reused in the time dimension. With these characteristics, decisions on line-side storage of materials were introduced on the basis of material batching and tow-trains scheduling problems. An integrated decision–making mathematical model with the objective of minimising the number of deliveries was established. A hybrid endocrine-immune algorithm (HEIA) was proposed to jointly make decisions on the delivery batch, delivery time and storage positions of each job’s materials. Numerical experiments with the real-world data and randomly generated instances validate the effectiveness and efficiency of HEIA.     

基于灰色机会约束规划的不确定条件下车间作业调度

针对不确定条件下job shop调度问题的约束条件中含有灰色变量,提出用灰色机会约束规划方法解决不确定条件下job shop调度问题,建立了灰色机会约束规划调度模型.同时,使用灰色模拟的方法和手段解决了灰色机会约束规划问题.给出了如何使用灰色模拟技术处理复杂的灰色机会约束以及基于遗传算法的求最优解的过程,并提出用灰色模拟技术结合遗传算法求解生产调度问题中的灰色不确定规划问题.计算仿真结果表明,这种基于灰色机会约束规划的方法处理不确定条件下车间作业调度问题的模型是可行而有效的.     

A genetic algorithm based procedure for more realistic job shop scheduling problems

This work presents a robust procedure to solve job shop scheduling problems with large number of more realistic constraints such as jobs with several subassembly levels, alternative processing plans for parts and alternative resources for operations, requirement of multiple resources to process an operation (e.g. machine, tools, fixtures, staff), resource calendars, batch overlap and sequence dependent setups. Also, the approach considers multi-objective evaluation functions. The system uses modified schedule generation algorithms to obtain a set of initial solutions. Each initial solution is enhanced by a local improvement procedure. Then a hybrid genetic algorithm, which incorporates a local hill climbing procedure, is applied to the set of local optimum schedules.     

A batch scheduling model for m heterogeneous batch processor

This research addresses a batch scheduling problem for single item parts with multi due date on m heterogeneous batch processors. The objective is to minimise total actual flowtime of parts through the shop. The total actual flowtime of parts in a batch is the multiplication of the interval between batch arrival time and the due date by the number of parts in the batch. Using the actual flowtime as the objective means it is oriented to satisfy the due date as a commitment to customers, and simultaneously to minimise the length of time of the parts spending in the shop. An algorithm to solve this problem is proposed.