基于交货期紧迫度的综合调度算法

为解决开始时间与交货期都不相同的多品种小批量复杂产品综合调度问题,提出基于交货期紧迫度的综合调度算法。该算法根据产品加工的开始时间由前到后排序调度;当存在多产品开始时间相同时,根据产品优先加工的紧迫度,确定它们的调度次序;如果存在紧迫度相同的产品,将按交货期由早到晚排序调度;若交货期也相同,则将它们虚拟成一个产品统一调度;对被调度产品采用长路径策略和短用时策略确定其各工序的调度次序,并结合设备工序紧凑法确定工序的开始时间。该算法结合产品紧迫度和设备工序紧凑法的优点,使开始时间不同的多产品在尽量减少设备空闲时间的情况下,按交货期完工。理论分析和实例表明,该算法可在二次复杂度内给出较合理的综合调度方案。     

基于设备空闲事件驱动的综合调度算法

针对基于拟关键路径法(Allied criticai path method,ACPM)的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理,使设备产生较多空闲时间的问题,提出基于设备空闲事件驱动的综合调度算法.该算法主要是根据空闲设备选择加工工序,思路是以每次工序加工结束作为一次设备空闲事件,驱动空闲设备进行一次可调度工序的寻找:如果可调度工序唯一,则调度此工序;如果可调度工序不唯一,选择父结点路径长的工序;如果父结点最长路径相同,选择用时短的工序.由于该算法在调度工序时不考虑工序序列且以设备空闲驱动,使得该算法按工序并行处理且能充分利用设备空闲时间,避免基于ACPM法产生较多设备空闲时间的问题.另外,由于该算法无需判断空闲时间段的大小、相同设备间的使用均衡和无需空闲设备频繁检测可调度工序,可节约大量的判断操作.实例表明所提出的算法不仅比系列ACPM法设备利用率都高,而且简便可行.     

存在设备无关延迟约束的综合柔性调度算法

针对加工和装配综合的柔性调度中忽略工序间存在设备无关延迟约束导致调度结果不精确的问题,提出存在设备无关延迟约束的综合柔性调度算法。该算法通过将设备无关延迟时间转换为设备无关延迟工序,提出存在设备无关延迟约束的综合柔性调度工艺模型;通过将设备无关延迟约束工序转换为顺序约束工序的策略,将存在设备无关延迟约束的柔性加工问题转换为一般柔性加工问题;对一般柔性加工问题采用短用时策略和设备均衡策略确定标准工序的加工设备,将一般柔性加工问题简化为一般综合调度问题并用长路径优先策略调度;对于路径长度相等且在同一设备上加工的标准工序,提出调度前续短路径策略选择调度工序。实例表明,该算法通过考虑设备无关延迟约束时间使综合柔性调度的结果更精确并且能减少产品总的加工时间。     

存在多设备工序的综合调度算法

针对工序集中存在需要多台设备协同完成加工的多设备工序的综合调度问题,提出一种把多设备工序设计成在多个相关设备上同时加工的多个虚拟工序的方法。该算法把产品加工树转化为多设备工序被设计成虚拟工序组的虚拟加工工艺树,为了优先调度虚拟工序组,将虚拟加工工艺树分解为以虚拟工序组为根结点的子树和剩余标准工序组成的子树,优先调度以虚拟工序组为根结点的子树;当以虚拟工序组为根结点的子树不唯一时,按子树上虚拟工序组个数多少确定子树的调度次序;对每个以虚拟工序组为根结点的子树,优先调度虚拟工序组个数较多的路径上工序;为了使相关虚拟工序同时开始加工,提出虚拟工序动态调整策略。理论分析和实例表明,所提出的调度算法能够较好地解决存在多设备工序的综合调度问题。     

存在预启动设备的综合调度算法

针对目前综合调度研究中没有考虑存在预启动设备的情况,忽略预启动时间对整体加工时间影响的问题,提出存在预启动设备的综合调度算法.该算法在预启动设备处于空闲状态时采用提出的预启动长路径优先策略,在预启动设备处于工作状态时采用提出的预启动短路径优先策略,以提高预启动设备的并行化和减少了设备的预启动次数;采用提出的调整序列确定策略,确定产生设备空闲时间段的工序为调整目标;采用提出的可调序列工序调整策略,对产生设备空闲的工序的前序工序按层序对其加工时间进行调整,以提高设备的利用率.实例说明提出的算法解决了存在预启动设备的综合调度问题,有一定理论和实际意义.     

考虑层级调度次序的资源协同综合调度算法

针对同层工序数量较多的多品种单件或小批量复杂产品的综合调度问题,以优化产品加工的时间成本和提高设备利用率为目标,提出了考虑层级调度次序的资源协同综合调度算法。算法设计了三级调度策略,首先是优先级调度策略,提高了工序间纵向加工的紧密度;其次是叶节点调度策略,实现了横向工序的并行优化;最后是短用时调度策略,充分利用了设备的空闲时间,提高了设备利用率。利用基于Petri网的生产过程模型进行调度仿真,实验结果表明了算法的有效性和可行性。     

基于择时的二车间综合调度算法

针对现有二车间综合调度算法在处理具有相同设备资源的二车间综合调度问题时,注重工艺树的横向并行处理,忽略纵向串行工序之间的紧密度,将二车间均衡处理或减少工序迁移次数一并做为调度目标导致不必要时间开销的问题,提出了基于择时的二车间综合调度算法。同时,提出了工序序列排序策略,将加工工艺树划分为若干工序序列,并根据其路径长度确定调度次序;提出了二车间择时调度策略,为工序寻找加工开始时间和加工车间,生成使当前部分产品加工总用时最小的工序调度方案。若该方案不唯一,则选择在二车间中该工序加工结束时间最早的工序调度方案。所提算法既保证了并行工序的并行处理,又有效地提高了串行工序的紧密度,避免了无效工序迁移带来的时间开销。通过实例说明了所提算法的有效性。     

基于关键设备工序紧凑的工序分类、分批的Job-Shop调度算法

通过对产品加工树的分解,可将产品加工工序分为存在具有唯一紧前、紧后相关工序和独立工序,在对这两类工序研究分批综合应用拟关键路径法(ACPM)和最佳适应调度方法(BFSM)调度时,考虑关键设备的工序紧凑性。通过分析与实例验证,所提出的调度方法对解决复杂Job-Shop调度问题不仅算法简练而且效果较好。     

基于邻域渲染的二车间综合调度算法

针对如何将复杂产品工序有效地分配到具有相同设备资源的两车间加工的问题,提出了基于邻域渲染的二车间综合调度算法。该算法为了实现产品加工尽早结束,提出关键设备均衡策略,将关键设备上的所有加工工序预先按并行加工时间最长方案均衡的分配到二车间;为了减少两车间之间的迁移次数,提出邻域渲染策略和同设备工序车间选择策略,通过计算未分配加工车间工序的邻域加工工序的渲染因子和影响因子确定其所在的加工车间;为了提高调度效率,采用动态关键路径策略和短用时策略确定工序调度次序,按序确定工序的加工车间和开始加工时间。分析和实例表明,所提出的算法产品加工时间较短、工序迁移次数较少且不增加算法复杂度。     

电机产品加工的动态调度算法

考虑多个具有不同开始时间的电机产品加工动态调度问题，将产品加工树的工序，分为具有唯一紧前或紧后工序的相关工序和独立工序两类，提出相关工序调度的拟关键路径法和独立工序调度的最佳适应调度法。结合拟关键路径法和最佳适应调度法，提出考虑关键设备的工序紧凑的多产品动态调度算法。实例数据表明，动态调度算法在总加工时间方面比一般启发式算法更短，适合于有不同开始时间的多产品动态调度环境。     

2个加工时间不同工序组批的嵌套批综合调度算法

针对已有的批加工工序数为2的批综合调度算法,没有考虑组批工序不同和后续工序中存在组批工序的情况,不能适用于更复杂的批综合调度问题,提出求解2个加工时间不同工序组批的嵌套批综合调度算法。该算法根据批处理工序加工时间不同的特点,定义串行衔接时间和并行衔接时间;提出判断组批的余差比较策略;当可与等待工序一同批处理的工序不唯一时,采用组批前移最大化策略确定组批处理工序;当准备组批处理工序的后续工序中存在组批工序时,在余差比较策略中加入嵌套优化策略确定该工序是否组批;由于组批工序的后续工序较多且对调度结果影响较大,采用前续工序优先策略使组批工序尽早加工。理论分析和实例表明,提出的算法可解决2个加工时间不同工序组批的嵌套批综合调度问题。     

A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem

This paper considers a single batch machine dynamic scheduling problem, which is readily found in the burn-in operation of semiconductor manufacturing. The batch machine can process several jobs as a batch simultaneously, within the capacity limit of the machine, and the processing time is represented by the longest processing time among all jobs in a batch. For a single batch machine problem with arbitrary job release time, we proposed an improved algorithm (merge-split procedure) to refine the solution obtained by the LPT-BFF heuristic, and two versions of a hybrid genetic algorithm (GA) are introduced in this paper. Each version of the hybrid GA diversifies job sequences using the GA operators in stage 1, forms batches in stage 2, and finally sequence the batches in stage 3. The difference is that merge-split procedures are involved in the second version of the hybrid GA. Computational experiments showed that the hybrid GA would obtain satisfactory average solution quality and the merge-split procedures would be good at reinforcing the solution consistency of the hybrid GA.     

面向配做的柔性生产线调度

配做是精密加工中常用的方法,它增加了调度约束和调度的难度。为解决这一难题,在对各种调度约束标准化的基础上,进行了适于配做的调度操作标准化技术和启发式调度算法的研究,保证了调度解的正确性并实现了调度解的快速生成,在此基础上进行了调度解优化技术和调度评估方法的研究,最终实现了人机协同的调度、评估一体化,为配做生产提供了有效的调度工具。     

Flexibility analysis of a surface mount technology electronic assembly plant: An integrated model using simulation

This paper focuses on developing an integrated model using simulation to evaluate the effect of several independent variables on the performance of a surface mount technology (SMT) production line. Real data and an existing SMT line from a high product mix/low volume electronics manufacturer are used to conduct the analysis. The independent variables used are set-up formation policies (group technology based family grouping methods), machine feeder types, similarity factor in set-up formation, parts reduction at design step of products, and inter-families and intra-family scheduling rules. In addition, a new method of grouping products is proposed. The measures of performance evaluated by the model are average lead time, average work-in-process (WIP) inventory and average set-up time. Data analysis shows that the proposed method of grouping products will reduce set-up time and lead time while slightly increasing WIP. The proposed simulation model helps assess the effects of some of the independent variables on line performance. Recommendations are made in order to help the user choose the best alternative to improve production line productivity and flexibility.     

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

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

基于多目标决策的车间作业调度算法研究

为解决具有多目标约束的Job-shop问题，提出了一种利用模糊综合评判规则和优先分配启发式算法相结合的调度算法。首先，用层次分析法给出各评判目标的评价权重；再由模糊综合评判规则确定目标权重下零件各工序所用的加工机床；最后，利用优先分配启发式调度算法确定在同一台机床上加工的各零件的先后顺序。实验结果证明了算法的有效性。     

Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine

Preventive maintenance (PM) planning and production scheduling are among the most important problems in the manufacturing industries. Researchers have begun to investigate the integrated optimization problem of PM and production scheduling with a single objective. However, many industries have trade-offs in their scheduling problems where multiple objectives must be considered in order to optimize the overall performance of the system. In this paper, five objectives, including minimizing maintenance cost, makespan, total weighted completion time of jobs, total weighted tardiness, and maximizing machine availability are simultaneously considered to optimize the integrated problem of PM and production scheduling introduced by Cassady and Kutanoglu. Multi-objective genetic algorithm (MOGA) is used to solve the integrated optimization problem. To illuminate the conflicting nature of the objective functions, decision-makers’ preferences of the multiple objectives are not integrated into the MOGA. The total weighted percent deviation, which represents not only the preferences of the objectives but also the deviations of the solutions, is proposed to help decision-makers select the best solution among the near-Pareto optimal solutions obtained by the MOGA. A numerical example reveals the necessity and significance of integrating optimization of PM and production scheduling considering multiple objectives.     

A Tabu Search Algorithm for Single Machine Scheduling with Release Times,Due Dates,and Sequence-Dependent Set-up Times

In this paper, we present a tabu search algorithm that schedules N jobs to a single machine in order to minimise the maximum lateness of the jobs. The release times, due dates, and sequence-dependent set-up times of the jobs are assumed to exist. We modified the original tabu search method to be suitable for the scheduling problem. The proposed tabu search algorithm is composed of two parts: a MATCS (modified apparent tardiness cost with set-ups) rule for finding an efficient initial solution, and the tabu search method to seek a near optimal solution from the initial solution. The experimental results show that the tabu search algorithm obtains much better solutions more quickly than the RHP (rolling horizon procedure) heuristic suggested by Ovacik and Uzsoy.     

Integrated optimization of production planning and scheduling for a kind of job-shop

This paper addresses an integrated job-shop production planning and scheduling problem with setup time and batches. It not only considers the setup cost, work-in-process inventory, product demand, and the load of equipment, but also the detailed scheduling constraints. That is a way different from the traditional hierarchical production planning method. The hierarchical methods do not consider the detailed scheduling constraints, so it cannot guarantee to obtain a feasible production plan. Here the integrated problem is formulated as a nonlinear mixed integer program model. And in order to simultaneously optimize the production plan and the schedule, an improved hybrid genetic algorithm (HGA) is given. In the model, the detailed scheduling constraints are used to compute the accurate load of a device in order to obtain a feasible production plan. The heuristic scheduling rules such as the shortest processing time (SPT) and the longest processing time (LPT) are used to generate a better initial solution. Also, a subsection coding strategy is offered to convert the planning and scheduling solution into a chromosome. At last, a comparison is made between the hybrid algorithm and a hierarchical production planning and scheduling method, showing that the hybrid algorithm can solve the problem effectively.