带有链优先约束工件的平行机排序问题

提出一种工件之间带有链优先约束的平行机排序问题,目标函数为极小化最大完工时间,优先约束为n条链Ti(1≤i≤n,n为任意实数),处理机为m台同速机,用三参数法表示为Pm|chains|Cmax.问题Pm|chains|Cmax是强NP完备的,利用启发式算法的最长加工时间优先规则,给出了一个多项式时间的近似方案.     

带服务等级约束的单位长度工件排序问题

研究带服务等级约束的等工件长度排序问题。对该问题的离线情形,给出了求解最优解的线性时间算法。对带有两个服务等级的在线情形,证明了该问题的下界为3/2,并给出了两台机上的最优在线算法。     

工件可拒绝的单机无界平行批排序

首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题.证明了问题1｜B≥n,rej｜ Tmax+ TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法.     

带模具约束的两台同型机排序问题的改进算法

研究带模具约束的两台同型机排序问题,针对极小化工件最大完工时间的目标函数,与已有的■近似算法相比,增加对最大工件集的处理,得到改进算法的近似比为■,并给出了紧例。     

带冲突约束两台平行专用机排序的一个改进算法

研究带冲突约束的两台平行专用机排序问题的一种特殊情形,针对极小化工件最大完工时间的目标函数,与已有的■近似算法相比,考虑了一类专属工件的加工,并对时间窗口作出改进,得到新算法的近似比为■,并给出了紧例。     

带服务等级约束的单位长度工件排序问题

研究带服务等级约束的等工件长度排序问题.对该问题的离线情形,给出了求解最优解的线性时间算法.对带有两个服务等级的在线情形,证明了该问题的下界为3/2,并给出了两台机上的最优在线算法.     

“合成链”算法与一类链优先约束的单机分批排序问题

讨论问题1|chains,B|Cmax具体可描述为:有n条链,其中一条链上有n个工件,其余的n-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间。我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出"合成链"算法,给出了时间复杂性为O(nk))的多项式时间算法     

一类工件有尺寸且分两次到达的在线分批排序

研究了工件有尺寸大小,有到达时间的在线分批排序,目标函数为工件的极大完工时间。就所有工件有2个到达时间的在线分批排序,给出算法,并证明了算法的竞争比不超过3。     

一类带时间约束的多工件排序优化

研究了多个工件在多台机床上顺序加工,满足不同工件时间约束下总体加工时间最短的排序问题。建立了该问题的0-1整数优化模型,编写了基于LINGO软件的求解方程,算例表明了该模型的有效性。     

单机带库存约束的排序问题

研究了一类单台机上带有库存约束的排序问题,目标函数是极小化加权完工时间总和。针对问题,首先证明了问题是NP-困难的,接着给出贪婪算法,证明了该算法的最坏情况界是无穷大,但随机试验表明算法的平均性能是令人满意的。     

Algorithms for single machine scheduling with availability constraints

It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dlmensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-ease performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.     

一类三阶段供应链排序问题的近似算法

主要研究一类三阶段供应链排序问题。储存工件的仓库和工厂在不同的地点,工件加工前需要从仓库运到工厂,加工完后再运回仓库。文中分别考虑了两个模型,第一个是两辆有容量限制的同类型车和单台机;第二个是一辆车和两台平行机。目标函数是极小化最后一个工件运回仓库的时间。针对两个模型,提出了相应的近似算法并证明其最坏情况界分别为2和2＋2λ-1^-1（其中λ〉1）。     

钢铁生产中管坯加热的单机连续型批调度策略研究

连续型批处理机调度问题是从钢铁生产线提炼出来的一种新型的批调度模型,该调度模型中,批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量。研究目标函数为最小加权总完工时间的单机连续型批调度问题,分析最优解的性质,讨论最优的批内、批间序及分批策略,给出工件权值与加工时间逆序情况下的动态规划算法。     

使两台和三台平行机的最小完工时间为最大的线性算法

讨论使两台和三台平行机的最小完工时间为最大的线性算法——对偶阈值算法DA m(ε),其中ε是参数。对于问题P2||Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3||Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11。这些都是线性时间算法中使最坏情况界值为最小的算法。     

Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints简

To solve the scheduling problem of dual-armed cluster tools for wafer fabrications with residency time and reentrant constraints, a heuristic scheduling algorithm was developed. Firstly, on the basis of formulating scheduling problems domain of dual-armed cluster tools, a non-integer programming model was set up with a minimizing objective function of the makespan. Combining characteristics of residency time and reentrant constraints, a scheduling algorithm of searching the optimal operation path of dual-armed transport module was presented under many kinds of robotic scheduling paths for dual-armed cluster tools. Finally, the experiments were designed to evaluate the proposed algorithm. The results show that the proposed algorithm is feasible and efficient for obtaining an optimal scheduling solution of dual-armed cluster tools with residency time and reentrant constraints.     

带多重加工前约束的单机MOPJ调度方法

为有效解决晶圆加工过程中带换模时间、品种间晶舟分配的不确定性以及参数调整等多重加工前约束的单机单作业多订单MOPJ(multi-order-per-job)调度问题,对问题域进行描述,以订单总完成时间最小为优化目标,建立数学规划模型.给出求解较优调度解的定理,并提出具有双层嵌套编码机制的混合差分进化的入侵杂草调度算法,该算法引入具有学习机制的算子以改善解的质量.为有效提高算法的收敛性,在变异及邻域操作中考虑自适应过程.仿真实验结果表明,该算法是有效且可行的,优化晶舟分配的调度较未优化的调度可提高至少10%的性能.     

Try and error-based scheduling algorithm for cluster tools of wafer fabrications with residency time constraints

To improve the productivity of cluster tools in semiconductor fabrications, on the basis of stating scheduling problems, a try and error-based scheduling algorithm was proposed with residency time constraints and an objective of minimizing Makespan for the wafer jobs in cluster tools. Firstly, mathematical formulations of scheduling problems were presented by using assumptions and definitions of a scheduling domain. Resource conflicts were analyzed in the built scheduling model, and policies to solve resource conflicts were built. A scheduling algorithm was developed. Finally, the performances of the proposed algorithm were evaluated and compared with those of other methods by simulations. Experiment results indicate that the proposed algorithm is effective and practical in solving the scheduling problem of the cluster tools.     

带有路径和运输方式选择的供应链排序算法研究

主要研究了在供应链中具有单台机器的单个制造商、多个客户的生产和运输的集成排序问题。以生产排序和运输的总费用达到最小作为目标函数。其中生产排序费用是用工件送达时间的函数表示,发送费用是由固定费用和可变费用组成,可变费用与路径和运输方式的选择有关。对该问题的两类特殊情形给出了基于动态规划的多项式时间算法。     

一般约束优化含等式约束问题的鲁棒信赖域算法

针对一般约束优化问题进行了研究.利用引入罚函数将一般约束问题转化为一个只含不等式约束的的参数规划问题的技巧,将不等式约束优化问题的一个鲁棒信赖域算法扩展到一般约束优化问题中,并保留了算法的良好性质;同时,在一定条件下,得到了算法的全局收敛和超线性收敛.     

A two-stage flexible flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage

This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡a （j∈N）, and the processing time of job Jj is bj（j∈N） on a batch processorM. We take makespan （Cmax） as our minimization objective. In this paper, for the problem of FSMP-BI （m identical parallel machines on the first stage and a batch processor on the second stage）, based on the algorithm given by Sung and Choung for the problem of 1 ｜ri, BI｜Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max {O（nlogn）, O（nB）} time. A max {O（nlogn） , O（nB）}time symmetric Algorithm H2 is given then for the problem of BI-FSMP （a batch processor on the first stage and m identical parallel machines on the second stage）.