加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O（n^k+2/（k-1）!）.同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O（（2n+m+n log n）n^k-1/（k-1）!）.     

机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

一类带核的平行机排序问题

研究了一类工件具有相似加工时间的带核的平行机排序问题,运用ＬＰＴ算法求解,得到ＬＰＴ算法界的精确估计并对问题的某些情形,给出了界紧的例子。     

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

加工时间可控的单台机器排序问题的近似算法

本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法.     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

云制造中带学习效应平行机排序问题的最优可中断算法

研究了云制造环境下一类带有学习效应的m台平行机排序问题.每台机器都有一个不同的单位时间加工费用,目标是在不超过给定的总费用情况下,从m台机器中选取若干机器加工工件,极小化最大完工时间.考虑了机器加工费用依赖于时间变化的学习效应函数.分别针对基于指数函数和幂函数的两类学习效应函数,分析了最优排序的性质并给出了最优可中断算法.     

可拆分有调整时间的平行机排序问题的一个算法

考虑有独立调整时间的同型号平行机排序问题,极小化最迟完工时间,产品允许拆分,同一产品被拆分后各部分可以在不同机器上同时加工,该问题是ＮＰ－ｈａｒｄ问题。本文首先给出该问题的一个启发式算法ＭＬ,然后证明了其最坏情况估计不超过７／４－１／ｍ（ｍ≥２）。     

Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

延误工件个数与最大加工时间压缩比例之和的可控排序

研究工件加工时间可控的排序问题，讨论的目标函数是延误工件个数与最大加工时间压缩比例之和，证明这一问题是多项式时间可解的。     

非线性加工时间单机排序问题

讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论.     

一台机器在加工时间相同准备时间可控时的Lmax问题

一组ｎ个工件需在一台机器上加工，工件ｊ所需的加工时间，应交工时间、准备时间分别为ｐｊ、ｄｊ、ｒｊ＾０，准备时间可压缩量为ｘｊ，０≤ａｊ≤ｒｊ＾０，压缩权因子为ωｊ由最大延误Ｊｍａｘ和压缩费用∑ωｊｘｊ可构成文中（Ｐ１）－（Ｐ３）三个排序问题，在ｄｊ＝０的条件下，引文「１」的作者证明了（Ｐ１）、（Ｐ３）为强ＮＰ－Ｃ的。本文在ｄｊ任意，ｐｊ＝ωｊ＝１的条件下，对（ｐ１）－（Ｐ３）给出了一个伪多项式时间     

Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

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

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

具有一般学习效应的单机排序问题

在具有学习效应的环境下,由于机器重复加工相同或相似的工件,因此以后加工的工件的加工时间变小.本文研究新的更一般的学习效应:Dejong学习效应.我们证明单机最大完工时间问题,总完工时间问题和两类多目标问题是多项式时间可解的.