加工多类型晶圆的集束型装备调度模型

研究了加工多类型晶圆和有滞留时间约束的集束型装备调度问题,其中包括晶圆排序和双臂机械手搬运作业排序两类问题.分别推导了三类不等式约束条件,包括加工模块处于加工和空闲两种状态下的滞留时间约束、任意单个和两个搬运作业情况下的机械手搬运能力约束,以及加工模块能力约束,建立了以最小化生产周期为目标的混合整数规划模型.典型生产实例和随机算例的仿真结果验证了模型的可行性和有效性.     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

客户订单多分离点对加工装配型产品的生产成本影响研究——装配延迟视角

大规模定制需要确定客户订单分离点(CODP),而CODP确定依据之一就是分析其对生产成本的影响。本文基于装配延迟视角,通过分析延迟生产系统中的生产成本构成问题,在探讨标准模块和变型模块特点基础上,将加工装配约束、变型模块差异化和客户订单提前期作为约束条件,综合考虑加工成本和库存成本,构建多个CODP对加工装配型产品的生产成本影响模型,并分析生产成本函数的变化趋势从而选择合适的CODP定位点,最终通过算例仿真对该模型进行了验证。     

战时备件配送的MDVRPTW问题研究

战时备件配送的车辆调度是提高装备保障效率的关键因素.以装备效能损失最小化为车辆调度的目标,建立了问题的M DVRPTW模型,并应用蚁群算法对问题进行了求解.算法中,根据问题特征改进了状态转移规则,设计了串行和并行两种路线构造方法,并应用局部搜索模块对蚂蚁构造的路线进行改进.对算例的计算实验表明,串行路线构造方法在精度和速度两方面均优于并行路线构造方法.     

考虑运输时间的MapReduce模型下的同类机调度研究

MapReduce模型在大数据处理及机器调度方面日趋重要.针对MapReduce模型中的每个工件由Map和Reduce两道加工工序组成,其中Map工序允许分割成若干个子任务,并在多台同类机上并行加工,而Reduce工序只能在该工件的Map工序里的子任务全部加工完后才能启动加工,且Reduce工序不能分割,即只能在一台机器上连续加工.在实际生产中,重型工件的两个相邻工序若分配给不同机器,则工件在机器之间需要一定的运输时间.结合工件的到达时间约束,以最小化最大完工时间为目标,构建了混合整数规划模型,设计了采用单纯形差分变异策略的改进磷虾算法来求解模型.利用数值仿真实验,与基本磷虾算法、遗传算法及CPLEX计算结果进行对比.测试结果说明了所提出的改进磷虾算法在解的质量和运行时间方面均优于基本磷虾算法、遗传算法,验证了模型与算法改进的有效性.     

中间品储存约束的多工序批量加工排序问题研究

本文结合生产实际情况，考虑了有限的中间品储存能力所带来的影响，对具有中间品储存约束的多工序批量加工排序问题进行研究。文中利用状态-任务-网络概念和层级模型方法，构建了基于混合整数线性规划的修正排序模型，应用标准优化软件求解。最后用一个算例来说明所构建模型的有效性。     

汽车滚装码头泊位调度优化模型与算法研究

本文研究滚装码头混合泊位分配和劳动力分配的联合调度优化问题。首先,考虑潮汐时间窗约束、装卸劳动力约束、泊位缆桩分布约束以及泊位不规则布局因素,建立以最小化船舶总服务时间为目标的混合整数规划模型。其次,采用内外嵌套算法设计策略,提出求解该类问题的组合算法。其中,外层是多种群并行进化的遗传算法,生成多种船舶计划顺序,内层为基于规则的启发式算法,用于计算给定计划顺序的目标函数值。然后,基于实际运营数据,生成多组不同规模的算例进行全面数值实验,结果表明所提出的算法可在10分钟内求解包含50艘船、100个泊段的算例。最后,开展基于真实滚装码头运营实例的案例分析,对所提模型和算法在实际码头调度问题中的适用性与高效性进行验证。     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

基于贝叶斯一稀疏约束正则化方法的地震波形反演

将稀疏约束正则化方法应用于地震波形反演问题.为了减弱对稀疏约束项的光滑性要求,引入贝叶斯推断,产生一组收敛于后验分布的采样点.通过数值算例记录了采样点的条件期望、方差、置信区间等具有统计意义的结果.数值结果表明,在没有光滑性的要求下,稀疏约束正则化方法对孔洞模型和分层模型中的介质边缘有良好的识别能力.特别地,当减少观测数据时,稀疏约束正则化方法仍能获得较好的反演结果.     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

Flexible hiring in a make to order system with parallel processing units

In this paper, we study a make-to-order production system with parallel, identical processing units. Each order needs to be satisfied on a single processing unit that is run by a crew. The inter-arrival time and the service time for each order are random variables. The system operates under a lead time performance constraint, which demands the completion of each order within a pre-determined lead time with a certain probability. The minimum number of processing units needed to satisfy this constraint is determined at the tactical level. Our research focuses on the cost savings that can be realized with the use of flexible crews via contractual hiring agreements with an External Labor Supply Agency (ELSA). The ELSA can periodically provide an agreed number of crews. The cost incurred for a flexible crew is higher than that for a permanent crew, and is decreasing in the period length. We model and analyze this system using the transient behavior analysis of multi-server queues and propose several empirically testable functions for the cost of flexible crews. In our computational study, we demonstrate possible cost savings of 2-level, threshold type hiring policies, relative to the fixed capacity system, under 9 scenarios with three demand-to-processing rate ratios and three lead time performance constraints, each of which reflects a different level of ambition. We observe that the maximum savings occur when the cost of a flexible crew is same as that of a permanent crew, and range from 29.38% to 50.56%. However, as the flexible crews become more expensive, the system may choose to employ permanent crews only. We observe that cost savings consist of two parts: savings due to the cancellation of the sclerosis of capacity discreteness, and savings due to the use of workload information in hiring actions. The latter part is higher for more ambitious lead time performance constraints, and for higher mean processing times. Finally, when there is an additional cost for transacting an agreement with the ELSA, we observe that the capacity flexibility option loses its charm, especially if the transaction cost is higher than the cost of a permanent crew.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

Makespan minimization in online scheduling with machine eligibility

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area.     

Makespan minimization in online scheduling with machine eligibility

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.     

高速转发引擎设计分析与实现

高速转发引擎是核心路由器设计中的重要难点和关键技术,基于FPGA技术,分析了高速转发引擎设计中的挑战,并给出了一种基于并行流水线机制的10Gbps转发引擎设计方案.     

MILP-based approaches for medium-term planning of single-stage continuous multiproduct plants with parallel units

In this paper, we address the problem of medium-term planning of single-stage continuous multiproduct plants with multiple processing units in parallel. Sequence-dependent changeover times and costs occur when switching from one type of product to another. A traveling salesman problem (TSP)-based mixed-integer linear programming (MILP) model is proposed based on a hybrid discrete/continuous time representation. We develop additional constraints and variables to ensure that subtours do not occur in the solution. The model is successfully applied to an example of a polymer processing plant to illustrate its applicability. In order to solve larger model instances and planning horizons, a rolling horizon approach is developed to reduce the computational expense. Finally, the proposed model is compared to a recently published approach through literature examples, and the results show that the computational performance of the proposed model is superior.     

Extension of an algorithm for product mix problems with fuzzy conditions

In the real world of production, there are some uncertain parameters such as capacity, profit, and processing time. On the other hand, the fuzzy sets theory is applied as a suitable tool for managing production where dynamicity of the production environment prevents from determining target function, constraints and other parameters of the model. In this paper, a genetic algorithm embedded in fuzzy revised theory of constraints is presented for product mix problems. Results of implementing the proposed algorithm show efficiency and flexibility of this algorithm.     

The wafer probing scheduling problem (WPSP)

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.