急件订单干扰下虚拟单元重调度

虚拟单元生产中,针对急件订单干扰情况,研究了考虑序位相似性,即尽量保持初始工序的加工次序的虚拟单元重调度问题。为了应对急件订单干扰,设置了各工件工序可用机器集合和相应的加工时间集合,构建了以序位相似性最大和急件订单完工时间、系统总流程时间最短为目标的多目标非线性整数规划模型。针对模型自身特征,采用了遗传—蚁群算法相结合的优化算法求解模型。最后,以船舶实际生产为例,验证了模型的可行和优越性,以及算法的有效性。     

制造单元布局问题的双目标模型与算法研究

单元制造系统的布局对于提高系统的效率起着十分重要的作用。以最小化物料周转量和设施面积为目标,建立了一个单元制造系统布局的双目标优化模型,在该模型中不同制造单元的布局、单元内部不同设施的位置与方向这几个问题可以同时进行优化。基于模拟退火邻域解的变尺度生成机制和双目标抽样准则设计了模型的求解算法。算例表明本文算法所得Pareto解集优于经典的NSGA-Ⅱ算法。     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

装配系统的供应链排序问题

在装配系统中,有多个供应商向同一个制造商提供零部件,仅当一个产品的所有零部件都送到后,制造商才进行最后的组装与发送.假设制造商为非瓶颈式生产.研究目标为工件带权完工时间和及最大延误的装配系统供应链排序问题,利用排序的理论和方法,分别设计多项式时间算法,并分析算法的性能比.     

加工时间可控单机加权总完工时间Pareto优化研究

针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。     

基于数据驱动与遗传计算的海域组合单元水质模型多参数分步耦合优化反演方法研究

考虑水质模型参数时域和地域差异性,建立了模型参数在各单元与时段内独立赋值的海域组合单元水质模型.结合多种反演方式的效率问题,通过数据驱动模型、遗传算法和海域组合单元水质模型的分步耦合,提出了水质模型多参数优化反演的新方法:将数据驱动模型同海域组合单元水质模型有机结合进行初步反演,获得多参数匹配关系;以误差函数为适应度,将海域组合单元水质模型嵌入遗传算法模型中,以多参数匹配关系初值为约束条件,进行多参数精确反演.最后以渤海湾海域组合单元水质模型多参数反演的"孪生"试验验证方法的有效性,数值结果表明分步耦合反演新方法具有较高的精度和效率;组合单元式的参数赋值与反演方式有利于提高模型验证精度.     

带有随机决策单元的广义数据包络分析方法

广义DEA方法是一种相对效率评价方法,解决了决策单元相对于任意参考系(样本单元集)的效率比较问题.在实际中,有时评价标准是确定的,决策单元的生产具有不确定性,有必要在进行生产之前基于确定性样本单元对随机性决策单元进行相对效率评价.为了解决这个问题,研究样本单元为确定值,决策单元为随机变量的广义DEA模型,分别通过期望值和机会约束将随机模型转化为确定性规划,给出决策单元GEDEA有效和GCDEA有效的概念,GEDEA有效与多目标规划Pareto有效关系,以及利用移动因子对决策单元进行有效性排序方法.     

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时,该问题等价于图上的最大匹配问题,因此存在组合强多项式时间算法;但量当机器台数为3或者多于3时,该问题是强NP困难的．     

曲线边界薄板弯曲问题的一种新单元：曲边四边形单元

本文提出了曲边四边形薄板弯曲单元解决曲线边界薄板的弯曲问题.文中给出了二维坐标的变换关系,由于引进了基于广义变分原理的附加刚度,使计算精度更高,计算机时相对缩短.通过算例,说明这种单元计算精度是相当高的。     

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.     

An optimal (Q,r) policy for a multipart assembly system under stochastic part procurement lead times

We consider an EOQ-type model for a simple production system, where a number of parts are acquired to produce a single product and the part procurement lead times are random. Assembly is instantaneous and takes place intermittently in batches but cannot start until all the parts are available. The problem is to simultaneously determine when to order each part and what lot size to produce, namely to determine the reorder point for each part and the assembly lot size, so that the average total cost per unit time, composed of the setup cost, inventory holding costs for the parts and the assembled product, and the shortage cost for the assembled product, is minimized. We then develop a tailormade solution method for this problem to obtain a global optimal solution by taking advantage of the structure of the problem formulation, where the nonlinear programming problem is decomposed into a family of subproblems parametrized by the average assembly delay time. Numerical experiments are then conducted for the case of twopart problems, and some interesting observations are made.     

Machine scheduling with a rate-modifying activity

Motivated by a problem commonly found in electronic assembly lines, this paper deals with the problem of scheduling jobs and a rate-modifying activity on a single machine. A rate-modifying activity is an activity that changes the production rate of the equipment under consideration. Hence the processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. The decisions under consideration are when to schedule the rate-modifying activity and the sequence of jobs to optimize some performance measure.In this paper, we develop polynomial algorithms for solving problems of minimizing makespan, and total completion time respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally.     

Scheduling of Products with Common and Product-Dependent Components Manufactured at a Single Facility

This paper analyses a scheduling problem concerned with the production of components at a single manufacturing facility where the manufactured components are subsequently assembled into a finite number of end products. Each product is composed of a common component and a product-dependent component, and completion time of a product is determined by the completion time of the last of two components. All the components are manufactured in a batch process at the single facility and, during the batch process, the manufactured components are individually moved to the next (assembly) station; switching from production of product-dependent components to common components only incurs a set-up cost. The solution properties are characterized subject to the mean flow time measure, based upon which an efficient branch-and-bound solution algorithm is exploited.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

Multi-product lot-sizing and sequencing on a single imperfect machine

A problem of lot-sizing and sequencing several products on a single machine is studied. The machine is imperfect in two senses: it can produce defective items and it can breakdown. The number of defective items for each product is given as an integer valued non-decreasing function of the manufactured quantity. The total machine breakdown time is given as a real valued non-decreasing function of the manufactured quantities of all the products. A sequence-dependent setup time is required to switch the machine from manufacturing one product to another. Two problem settings are considered. In the first, the objective is to minimize the completion time of the last item, provided that all the product demands for the good quality items are satisfied. In the second, the goal is to minimize the total cost of demand dissatisfaction, subject to an assumption that the completion time of the last item does not exceed a given upper bound. Computational complexity and algorithmic results are presented, including an FPTAS for a special case of the cost minimization problem, and computer experiments with the FPTAS.     

单台机以总完工时间为目标的批排序问题

研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+3~(1/2)/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n ⁷) time.