板式家具高速自动分拣系统出库及打包调度策略

为提升定制家具自动分拣系统出库及包装作业的整体效率,根据出库及包装作业的工作特点,将出库打包问题抽象为一类板件处理具有优先顺序约束及机器约束的三阶段柔性装配流水车间调度问题。在对各约束进行定义和数学描述的基础上,以最大出库完工时间、包装工位最大完工时间、板件平均等待时间三者加权和最小化为优化目标,建立了板件处理具有优先顺序约束和机器约束的三阶段柔性流水车间调度问题的数学模型;针对该模型,构造了一种启发式求解算法H~*。为验证算法的有效性,基于裂区试验设计的思想生成大量算例,并将启发式算法H~*与构造的9种组合规则算法、5种元启发式算法进行性能比较。结果表明,H~*算法可高效地获得高质量的解。     

基于模糊时间并具有成组约束的车间排序算法

针对模具制造过程工件到达时间和加工时间难以精确的特点,以最小化最大完成时间为调度目标,研究了前阶段带有成组约束的两阶段柔性同序加工车间的排序问题.借助模糊数学理论,将工件的加工时间和到达时间作模糊数处理,采用均匀分布的Lee-Li法将模糊数转化为精确值,通过遗传算法优化排序,应用企业实际算例仿真说明该算法的有效性和可行性.     

任务工时不确定的模具车间前摄性调度研究

由于模具生产属于非重复性生产模式,各工序的工时具有很强的随机不确定性,这给模具车间制定合理可行的作业计划带来了一定的困难。针对这一实际问题,提出了一种考虑任务工时不确定性的前摄性车间调度算法。首先,分析了模具精加工环节的两道关键工序对制造系统稳定性的影响,并基于工序的工时不确定特性,建立了任务工时不确定的离散概率模型;然后,以调度方案的稳定度作为优化目标,构建了两阶段流水车间前摄性调度模型,针对该模型,提出了一种变宽集束搜索求解算法;最后,将该算法与定宽集束搜索算法进行对比分析,结果表明该算法能很好地兼顾求解质量和计算时间。     

不相容工件族柔性流水车间批调度算法

热处理是模具生产过程的瓶颈工序。在由淬火和回火两道工序组成的模具热处理柔性流水车间中,工件存在材料类型、到达时间、交货期、重量和优先级差异。在存在差异工件和不相容工件族的条件下,以最小化加权总拖期量为调度目标,提出两种改进启发式算法和一种新的构建启发式算法。并构建另一种典型规则算法对比说明所提算法的有效性。通过大量实验数据验证,结果显示新的构建启发式算法有较好的运算性能,满足企业实际应用需求。     

考虑工件外协的模具热处理车间生产计划

热处理是模具制造过程的瓶颈工序,对整套模具的交货期和制造成本会产生重大影响。热处理车间的生产调度具有批调度特征。在两阶段柔性流水车间中考虑了工件外协,并将热处理车间的生产计划分成周期滚动计划、淬火阶段上机计划和回火阶段上机计划3个层次;以最小化制造成本为调度目标,分别构建这3个阶段的调度算法,并通过多种实验算例说明该算法的有效性。实验结果表明:设置最小等待重量策略的制造成本明显高于其他3种策略的调度成本,在不考虑工件外协的情况下,所提出的上机调度策略的调度结果略优于设置最大等待时间策略的调度结果,考虑工件外协的调度策略的结果是4种策略中最优的。     

考虑约束松弛的柔性流水调度研究

针对柔性流水车间作业调度问题,考虑加工批量约束松弛和瓶颈工序顺序松弛2种情形,抽取出相应的新型柔性流水车间调度问题,建立了最小化最大完工时间的数学模型,提出了改进的单亲遗传算法,进行了优化求解,得到了不同约束松弛情况下的最优调度方案。通过算例仿真,验证了所提方法的有效性。     

柔性流水车间设备利用率排产优化问题研究

针对具有工序约束信息的柔性流水车间的设备利用率优化问题,提出利用PSODE混合算法来解决该问题,全局优化过程采用群体优化算法,在局部优化过程中通过上下道关联工序约束信息来控制工件的分配,将并行工位总设备利用率作为适应度函数,构建了具有关联工序约束的柔性流水车间生产调度模型,确定生产工件的加工路径、加工顺序、开工时间和完工时间。通过多组方案数值计算结果对比分析,验证了PSODE算法解决柔性流水车间设备利用率优化问题的有效性。     

柔性流水车间调度模型与混合引力算法

针对柔性流水车间调度问题,利用机器特定事件点来描述工件的机器选择,再以最小化最大完工为目标,考虑工艺约束和时间约束构建了柔性流水车间调度的混合整数线性规划模型,用GAMS/Cplex找到小规模问题的全局最优解。为快速求解大规模问题的近优解,提出了结合瓶颈启发式的引力搜索算法,利用瓶颈移动技术和John Son方法的解码机制,寻找最小化最大完工时间的最优调度方案。实验结果表明,所提出的模型及算法能高效地求解以最小化最大完工时间为目标的柔性流水车间调度问题。     

具有工件约束的模具制造优化调度算法研究

为解决具有工件约束的模具制造优化调度问题,提出了一种利用蚁群算法和优先分配启发式调度算法相结合的调度算法。该算法能够方便地描述问题的约束条件的特点。首先,由蚁群算法确定模具零件各工序所用的加工机床,用节点模式下的有向图描述问题的解空间,用蚂蚁种子信息素踪迹更新策略对信息素进行更新,以获得问题的解;然后,利用优先分配启发式调度算法确定在同一台机床上加工的各零件的先后顺序。实验结果验证了算法的有效性。     

求解流水车间调度问题的瓶颈指向启发式算法

针对最小化时间表长的流水车间调度问题,提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。首先,为构建初始工件排序,充分利用各机器负荷一般不相等的特点,瓶颈阶段前加工时间较短而之后加工时间相对较长的工件优先开始加工;其次,当有工件等待加工时,根据工件在瓶颈机器前或后加工时间的特征调整工件加工顺序;最后,采用邻近工件成对交换和插入的方式改进初始调度。当瓶颈机器趋于中间阶段,或瓶颈机器上工件的加工时间趋于增加时,求解效果较好。数据实验表明算法是有效的。     

Performance Comparison of Some Classes of Flexible Flow Shops and Job Shops

Flexible manufacturing systems (FMSs) for two-stage production may possess a variety of operating flexibilities in the form of tooling capabilities for the machines and alternative routings for each operation. In this paper, we compare the throughput performance of several flexible flow shop and job shop designs. We consider two-stage assembly flow shops with m parallel machines in stage 1 and a single assembly facility in stage 2. Every upstream operation can be processed by any one of the machines in stage 1 prior to the assembly stage. We also study a similar design where every stage 1 operation is processed by a predetermined machine. For both designs, we present heuristic algorithms with good worst-case error bounds and show that the average performance of these algorithms is near optimal. The algorithms presented are used to compare the performance of the two designs with each other and other related flexible flow shop designs. It is shown, both analytically and experimentally, that the mode of flexibility possessed by a design has implications on the throughput performance of the production system.     

Scheduling of Flexible-Sequenced Process Plans in a Mould Manufacturing Shop

Process planning and scheduling used to be two very separate processes. However, owing to the recognition of the intricate relationship between them, recent work has focused on integrating the two processes. The use of flexible process plans in scheduling allows more flexibility in production and thus gives substantial cost savings. It also increases the solution space of the optimisation problem and makes it more critical to have an effective optimisation algorithm than for traditional scheduling problems. This paper describes a process-planning and scheduling system that makes use of the branch and bound approach to optimise priority weighted earliness of jobs scheduled in a mould manufacturing shop. Instead of consideing a flexible manufacturing system, this paper focuses on the demands of less integrated factories, which are especially typical of mould manufacturing shops. The layout of the system, the methodology of the algorithm and effectiveness of performance measures for real industrial use are discussed in the paper.     

Integrating lotsizing, loading, and scheduling decisions in flexible flow shops

Presenting an integrated lotsizing, loading, and scheduling model for the capacitated flexible flow shops with sequence-dependent setups is the main contribution of this paper. An exact formulation of the problem is provided as a mixed integer program. To solve this problem, mixed integer programming-based heuristics based on iterative procedures are provided. To test the accuracy of heuristics, two lower bounds are developed and compared against the optimal solution. The trade-offs between solution quality and computational time of heuristics are also provided.     

基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法

针对柔性作业车间调度问题,考虑自动导引车(AGV)在车间制造过程中只参与装卸和搬运工作,提出一种实现AGV路径规划与柔性作业车间调度集成优化的融合调度模型。采用基于工序排序与机器选择两个子问题的二维向量编码方案,并在解码过程中提出基于最先服务原则的AGV安排策略。对鲸鱼优化算法进行离散化改进,针对性地设计了多种种群初始化策略,引入遗传算法的交叉、变异操作以提升鲸鱼优化算法的全局搜索能力,并嵌入局部搜索算法以达到全局搜索和局部搜索的平衡,构建了一种混合遗传鲸鱼优化算法（HGWOA）来求解该融合调度模型。通过经典测试算例验证了算法性能,并使用正交试验优化了算法参数。研究结果表明,HGWOA算法用于求解柔性作业车间AGV融合调度问题可以获得较好的效果。     

A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks

In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow shop problem (FFSP). Flexible flow shops are thus generalization of simple flow shops. Flexible flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. FFSP can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. FFSP is known to be NP-hard. In this study, we present a particle swarm optimization (PSO) algorithm to solve FFSP. PSO is an effective algorithm which gives quality solutions in a reasonable computational time and consists of less numbers parameters as compared to the other evolutionary metaheuristics. Mutation, a commonly used operator in genetic algorithm, has been introduced in PSO so that trapping of solutions at local minima or premature convergence can be avoided. Logistic mapping is used to generate chaotic numbers in this paper. Use of chaotic numbers makes the algorithm converge fast towards near-optimal solution and hence reduce computational efforts further. The performance of schedules is evaluated in terms of total completion time or makespan (C_max). The results are presented in terms of percentage deviation (PD) of the solution from the lower bound. The results are compared with different versions of genetic algorithm (GA) used for the purpose from open literature. The results indicate that the proposed PSO algorithm is quite effective in reducing makespan because average PD is observed as 2.961, whereas GA results in average percentage deviation of 3.559. Finally, influence of various PSO parameters on solution quality has been investigated.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results.     

MULTI-SHOP SCHEDULING PROBLEM

A new concept of multi-shop (M ) is put forward which contains all basic shops including open shop (O), job shop (J ), flow shop (F ) and hybrid flow shop (H ) so that these basic shop can be scheduled together. Several algorithms including ant colony optimization (ACO), most work remaining (MWR), least work remaining (LWR), longest processing time (LPT) and shortest processing time (SPT) are used for scheduling the M. Numerical experiments of the M adopting data of some car and reC series benchmark instances are tested. The results show that the ACO algorithm has better performance for scheduling the M than the other algorithms, if minimizing the makespan ( C m*ax) is taken as the objective function. As a comparison, the separate shops contained in the M are also scheduled by the ACO algorithm for the same objective function, when the completing time of the jobs in the previous shop is taken as the ready time of these jobs in the following shop. The results show that the M has the advantage of shortening the makespan upon separate shops.     

不确定信息条件下Job-shop调度的混合智能算法

目前大多数生产调度的研究往往聚焦于经典调度问题的优化算法而忽略了车间中大量存在的不确定性，因而难以应用于实际车间调度。采用随机变量来描述真实车间中存在的一些不确定信息，在基于不确定规划理论的基础上建立了相应的不确定性调度模型，并研究了解决此类问题的混合智能算法。开发了混合智能优化原型系统，并结合仿真工具对该调度模型和混合智能算法进行了验证。