主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.     

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

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

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

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

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

工件带简单线性恶化函数和共同交货期单机排序问题

本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。     

一个双目标单机调度问题及其几个多项式可解情形

研究了一个双目标单机调度问题及其几个多项式可解的情形。问题的主目标是延误工件数最小,在此条件下,最小化各工件加权提前期的总和,由于该问题是NP一难的,故研究求解它的一个启发式算法及问题的几个多项式可解的特殊情形。     

考虑释放时间的单机JIT调度问题

本文主要研究二级供应链中的生产-库存-直接配送协同调度问题,其中存在一个制造商和多个零售商, 制造商根据订单进行生产, 然后将产品配送给零售商。该类问题可以抽象为考虑释放时间的单机JIT调度问题。借助于禁忌搜索算法, 本文提出了求解问题的CTA-TS算法, 并通过大量的实验数据与已有算法进行比较,说明了本文提出算法的有效性。     

工件带到达时间的两阶段柔性流水作业的近似算法

研究了工件带到时间的两阶段柔性流水作业的排序问题,基于求解流水作业和平行机问题的算法思想,提出两个相应的近似算法H(R)和H(MR(?)),证明了这两个算法的最坏情况性能比分别为3-1/m和2/5-1/m,讨论了界的紧性,并利用数值模拟以分析算法与最优值的近似性能比.     

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

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

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

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

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

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

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

具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。     

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

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

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

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

两类加工时间是一般函数的单机排序问题

考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.     

具有禁用区间的单机最小化加权完工时间和排序问题

研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.     

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.