Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.     

Optimal versus heuristic scheduling of surface mount technology lines

This paper presents and compares an exact and a heuristic approach for scheduling of printed wiring board assembly in surface mount technology (SMT) lines. A typical SMT line consists of several assembly stations in series and/or in parallel, separated by finite intermediate buffers. The objective of the scheduling problem is to determine the detailed sequencing and timing of all assembly tasks for each individual board, so as to maximize the line's productivity, which is defined in terms of makespan for a mix of board types. The limited intermediate buffers between stations result in a scheduling problem with machine blocking, where a completed board may remain on a machine and block it until a downstream machine becomes available. In addition, limited machine availability due to scheduled downtimes is considered. The exact approach is based on a mixed integer programming formulation that can be used for optimization of assembly schedules by using commercially available software for integer programming, whereas the heuristic approach is designed as a combination of tabu search and a set of dispatching rules. Numerical examples modelled after real-world SMT lines and some computational results are provided to illustrate and compare the two approaches.     

FMS Scheduling Simulation Based on an Evolution Algorithm

A FMS（flexible manufacturing system) scheduling algorithm based on an evolution algorithm (EA) is developed by intensively analyzing and researching the scheduling method in this paper.Many factors related to FMS scheduling are considered sufficiently.New explanations for a common kind of the encoding model are given.The rationality of encoding model is ensured by designing a set of new encoding methods,while the simulation experiment is performed.The results show that a FMS scheduling optimum problem with multi-constraint conditions can be effectively solved by a FMS scheduling simulation model based on EA.Comparing this method with others,this algorithm has the advantage of good stability and quick convergence.     

面向成套订单的生产与配送协调的排序研究

在工件体积和运输车辆容量的双重约束条件下,建立了以最大化成套订单数和最小化工件总配送时间的多目标规划模型,使用多目标排序寻找"约束解"的方法结合遗传算法求解此模型.最后通过算例分析,给出多目标规划模型及其综合算法在FLOW SHOP生产作业环境中的应用.计算结果表明,应用此模型和算法能够满足最大化成套订单数的要求,同时节省总的工件配送时间,有潜在的应用价值.     

Parallel flowshop scheduling using Tabu search

Production scheduling problems in manufacturing systems with parallel machine flowshops are discussed. A mathematical programming model for combined part assignment and job scheduling is developed. The objective of solving the scheduling problem is to minimize a weighted sum of production cost and the cost incurred from late product delivery. The solution of the model is NP-hard. To solve the problem efficiently, a heuristic algorithm combining Tabu search and Johnson's method was proposed. Several numerical examples are presented to illustrate the developed model and the algorithm. Computational results from these example problems are very encouraging.     

面向医疗器械企业灭菌工艺的不同容量平行机批调度

针对医疗器械企业灭菌工艺生产过程的调度问题,提出面向灭菌工艺的不同容量平行机批调度方法,建立以最小化总延迟时长、最小化总加工能耗和最大化灭菌柜装载率为目标的不同容量平行机批调度模型。并针对模型的求解提出一种改进的NSGA-III算法(Improved NSGA-III,INSGA-III)。为了获得更高质量的批调度解,采用EDT+MLC启发式规则生成INSGA-III初始种群,并设计一种局部搜索策略以改进算法迭代后期的搜索能力。最后,通过算例仿真与传统调度方法进行对比分析,验证了该模型和算法的有效性和可行性。结果表明,该模型和算法较传统调度方法有明显的优势,可为医疗企业实际生产调度提供新思路。     

Algorithms for multiprocessor scheduling with machine release times

In this paper we present algorithms for the problem of scheduling n independent jobs on m identical machines. As a generalization of the classical multiprocessor scheduling problem each machine is available only at a machine dependent release time. Two objective functions are considered. To minimize the makespan, we develop a dual approximation algorithm with a worst case bound of 5/4. For the problem of maximizing the minimum completion time, we develop an algorithm, such that the minimum completion time in the schedule produced by this algorithm is at least 2/3 times the minimum completion time in the optimum schedule. The paper closes with some numerical results.     

Quay crane scheduling with dual cycling

In this article, the dual cycling quay crane scheduling problem (D-QCSP) with hatches is addressed to minimize the operation cycles of quay cranes. The problem is decomposed into two sub-problems: the intra-group stage (sequencing stacks within each hatch) and the inter-group stage (scheduling all hatches). A new stack sequencing method is constructed for stacks of each hatch, which is modelled as a two-machine non-permutation flow shop scheduling problem. By removing inner gaps using left-shifting, the adapted hatch scheduling sub-problem is modelled as a two-machine grouped flow shop scheduling problem, which contains more precise processing times. A composite heuristic is proposed for the D-QCSP. Based on the derived lower bound, the heuristic is compared with the best existing heuristics on a large number of instances. Experimental results illustrate that the proposal outperforms the existing methods on all instances and dual cycling needs many fewer quay crane operating cycles than single cycling.     

考虑疲劳效应的伤员应急手术调度模型及算法

为了解决城市突发事件应急救援中批量应急手术的调度问题,并考虑医生长时间连续手术对手术持续时间和挽救病人生命的成功率带来的恶化效应,提出了三阶段批量手术调度模型,将应急手术调度看作是存在并行机的流水车间调度问题。利用改进的飞蛾扑火算法对应急手术模型进行求解,并通过实证来测试模型和算法的有效性。为了验证算法的性能,将经典飞蛾扑火算法、粒子群算法和布谷鸟算法与其对比,取20次运行结果,得知最大手术完成时间均值中改进的飞蛾扑火算法为最小,调度模型给出的调度方案中,3个救治阶段在时间维度上保持连贯。仿真结果表明,改进的飞蛾扑火算法能很好地求解批量手术调度模型,获得较好的调度结果。     

Efficient optimization of cyclic labor days-off scheduling

An efficient method is presented for the optimum solution of the cyclic manpower days-off scheduling problem. This method, which is based on linear programming, allows unequal costs to be considered for different days-off patterns. First, the solution of the dual linear programming model is used to determine the minimum workforce size. Then, a procedure based on the dual solution is introduced to assign the workforce to days-off patterns in order to minimize the total labor cost. The new method offers an alternative to specialized linear or integer programming software, since it requires only few and simple calculations.     

基于粒子群算法的半导体制造设备预维修调度

对半导体制造设备的预维修调度问题进行了研究,建立了半导体制造设备预维修调度的数学模型,分别提出了用于求解该问题的启发式方法和粒子群算法方案,阐明了两种算法方案的具体实现过程。通过对仿真实例进行计算和结果比较,表明了粒子群算法优于启发式方法,取得了不错的优化效果。     

供应链中生产和运输协调调度问题初探

提出了解决供应链中生产和航空运输协调调度问题的理论框架.基于对生产调度和航空运输调度彼此制约关系的分析,协调调度问题被分解为两个子调度问题.建立了航空运输子调度问题的整数规划模型,并证明了该问题为NP完全问题.提出了基于倒排调度方法(backward scheduling method)的调度算法解单机生产调度子问题.     

基于Benders分解的租赁车队规划

以汽车租赁业的日常车辆调配为背景,研究租赁车队的战术规划问题。将车辆调配情况抽象到时空网络结构中,并根据车辆需求的供应策略和时空节点的流量平衡得到约束条件,以企业运营成本最小为目标建立优化模型。针对模型特点采用Benders分解算法将原问题分解为两类子问题,给出对应的算法步骤。以一周为战术规划期设计算例,对模型和算法的有效性进行检验,结果表明能够为优化车队调配提供较好的辅助决策支持。     

Modelling and scheduling analysis of multi-cluster tools with residency constraints based on time constraint sets

This paper is dedicated to the scheduling problem of multi-cluster tools with process module residency constraints and multiple wafer product types. The problem is formulated as a non-linear programming model based on a set of time constraint sets. An effective algorithm called the time constraint sets based (TCSB) algorithm is presented as a new method to schedule the transport modules to minimise the makespan of a number of wafers. In approach, time constraint sets are maintained for all the resources and necessary operations to exploit the remaining production capacities during the scheduling process. To validate the proposed algorithm on a broader basis, a series of simulation experiments are designed to compare our TCSB algorithm with the benchmark with regard to cluster factor, configuration flexibilities and the variation of the processing times and residency constraint times. The results indicate that the proposed TCSB algorithm gives optimal or near optimal scheduling solutions in most cases.     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing

With the increasing prosperity of additive manufacturing, the 3D-printing shop scheduling problem has presented growing importance. The scheduling of such a shop is imperative for saving time and cost, but the problem is hard to solve, especially for simultaneous multi-part assignment and placement. This paper develops an improved evolutionary algorithm for application to additive manufacturing, by combining a genetic algorithm with a heuristic placement strategy to take into account the allocation and placement of parts integrally. The algorithm is designed also to enhance the optimisation efficiency by introducing an initialisation method based on the characteristics of the 3D printing process through the development of corresponding time calculation model. Experiments show that the developed algorithm can find better solutions compared with state-of-the-art algorithms such as simple genetic algorithm, particle swarm optimisation and heuristic algorithms.     

板式家具企业的订单组批问题研究

为了减少板式家具企业封边工序过长的准备时间以及提高原材料的开料利用率，满足企业快速组批的需求，本文研究板式家具的订单组批问题，并提出一个组批优化的方法。在对组批问题进行定义和数学描述的基础上，建立了一个双目标问题的数学模型，通过序贯优化分析如何求解双目标问题，设计出一种组合调度规则的启发式算法。为了验证算法和评估调度规则的性能，设计了该类问题的算例生成方法，并将本文的方法与另外构造的10种规则算法应用到生成的算例上，进行仿真调度，最后与精确解法作比较。仿真调度的结果显示基于板块颜色与板块厚度的调度规则可以有效地降低封边工序的准备时间，提高原料利用率。     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等，试验周期长、消耗大，因此如何缩短试验周期是亟待研究解决的问题．文中首先将试验流程优化问题转化为车间调度问题，建立了相应的数学模型，再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理．最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础．实例计算结果表明，该方法优化效果良好．     

遗传算法的双目标柔性作业车间调度研究

研究了FMS环境下先进制造车间路径柔性的优化调度问题.同时考虑现代生产准时制的要求,建立了柔性作业车间调度问题的双目标数学优化模型,并给出了求解模型的遗传算法的具体实现过程;针对模型的特殊性,提出了染色体两层编码结构,将AOV网络图应用到解码和适应度函数的计算中,通过一个调度实例进行验证,给出了相应的选择、交叉、变异操作设计方案.     

基于文化基因算法的开放车间调度问题研究

针对开放车间调度问题,运用了文化基因算法进行优化求解。在文化基因算法的框架中,既有种群中的全局搜索,又包含针对问题自身特点的局部搜索,为解决开放车间调度问题提供了一种新的算法。按照文化基因算法的思想和特点,将爬山法作为局部搜索策略加入到全局搜索策略所用到的遗传算法中,通过对开放车间调度问题的邻域结构进行研究,加入爬山搜索法进行优化求解。基于40个标准算例,通过与下界值的比较,验证了所提算法在解决具有较大搜索空间的调度问题时,其拥有更出色的算法性能。