随机需求下半导体生产车间的物流系统仿真优化

针对随机需求下具有“添加/卸除机器”特点的动态多阶段生产布局问题,建立其数学模型和批次到达速率公式.通过研究机器的添加/卸除规则,分析了添加和卸除机器事件以及3种调度准则,建立了随机需求下的仿真优化算法.通过算例验证了仿真优化算法的有效性以及仿真系统的有效性.     

同时具有学习效应和恶化效应的机器可用限制性排序问题

针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法.     

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

带机器准备时间的两台机器半在线排序

研究了两台机器的两个半在线排序问题.当机器为有准备时间的同类机时,总加工时间已知;当机器为有准备时间同型机时,最大加工时间已知.对这两个问题,给出了各自的半在线算法,证明了他们的竞争比分别至少为b 1/2b 1和2/3,其中b,为机器速度,b1=1,1＜b2=b.     

带到达时间、不可用区间、拒绝工件的单机排序问题 (三峡地区资源环境生态研究)

考虑的是带有到达时间、拒绝工件、不可用区间的单机排序问题。若工件被拒绝加工,厂家必须支付一定的拒绝惩罚;若工件被接受,则把工件放在机器上进行加工。机器带有不可用区间,在不可用区间内不能加工工件,并且在同一时刻至多加工一个工件。本文的目标函数是极小化所有接受工件的时间表长与所有拒绝工件的拒绝惩罚之和。首先给出了一个近似算法,并通过引理1证明出此算法是3-因子算法;其次提出了一个动态规划算法,然后通过修改这个动态规划算法的执行过程来减少运行时间,进而得到了一个全多项式时间近似方案,证明出该方案的时间复杂性为O(n2/ε)     

两台同型机多阶段维护调度问题的若干结果

研究了2种类型的机器维护:一种为周期性维护,另一种为决策维护.对于周期维护最小化时间表长问题,证明了经典的FFD算法是一个很好的启发式算法,并且得到了该算法的一个上界.对于决策维护最小化总完工时间问题,分析了SPT算法的界.特别地,对于单机并且机器仅需要2次维护的情况,给出SPT算法的界不超过11/9.     

机器带准备时间的平行机排序问题的并行阈值算法

针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε＝1/4时,此线性时间算法的最坏情况界为3/4.这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法.进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50 000个工件数量的规模下,具备很高效率.     

基于MAC的动态回溯算法优化

针对基于MAC的动态回溯算法在求解约束满足问题时, 不仅需要大量空间存储删除解释, 而且回溯机制过于复杂, 对经典的删除解释及动态回溯算法的回溯机制进行优化, 优化后的动态回溯算法减少了存储删除解释的空间, 并可仅使用一次回溯操作返回到可能导致冲突的关键变量. 在最差情况下, 存储删除解释的空间复杂度由O(n²d)改进为O(nd+n²). 通过结合restart技术使优化后的动态回溯算法成为完备算法. 实验结果表明, 优化后的完备动态回溯算法在大部分问题求解中, 整体效率明显优于标准回溯算法.     

零件加工路线柔性的测度及其应用

指出平行操作和多个可供选择的机器的存在是零件加工路线柔性产生的原因．采用根据熵的概念建立的零件加工路线柔性的测度，这一测度包含了所有的操作和机器特征（如机器可靠性等）．提出了制造系统中动态确定零件加工路线的算法．通过实例模拟对本算法和基于最短加工时间原则的算法进行了比较，结果表明基于最小熵原则的算法在提前期和机器利用率方面优于基于最短加工时间原则的算法     

零件加工路线柔性的测度及其应用

指出平行操作和多个可供选择的机器的存在是零件加工践张柔性产生的原因，采有根据的熵概念建立的零件加工路线柔性的测度，这一测度包含了所有的操作和机器特征（如机器可靠性等）提出了制造系统中动态确定零件加工践线的算法，通过实例模拟本算法和基于最短加工时间原则的算法进行了比较，结果表明基于最小熵原则的算法在提前和机器利用率方面优于基于最短加工时间原则的算法。