具有位置相关权重的工期分配排序问题研究

针对具有位置相关权重的工期分配排序问题进行了研究,其目标是在共同工期分配/松弛工期分配两种模式下,找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和,其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法,进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列,以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。

多目标物流配送优化问题建模及其遗传算法设计

建立了带有公共交货期的多目标物流配送优化模型,考虑了3层配送网络中物品分配和运输模式选择,并对迟到完成的任务给予惩罚,所优化的目标为总费用最小化和分拣中心负载的平衡。建立了一种遗传算法求解过程,对染色体采用了两部分编码,分别表示对分拣中心和运输模式的选择决策,并采用了可变的交叉和变异概率,以防止求解陷入局部最优。最后通过数值仿真试验表明了多目标问题求解的有效性。

一个带退化工件的单机准时生产制问题

研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(nlogn)时间的最优算法.

加工时间服从指数分布单机随机调度

讨论加工时间服从指数分布的单机随机调度问题 ,目标是实现工件完成时间与公共交货期偏差的加权和的期望最小化。此问题是 JIT(Just- In- Time)生产环境下的典型调度模型。结果表明问题的最优解关于权值与加工时间均值的商具有 Λ形特征。

随机加工时间的单机调度问题

讨论 n个独立工件在一台机器上加工。工件的加工时间服从正态分布 ,所有工件交货期设置公共交货期。目标是确定公共交货期及工件的最优排序 ,使工件完工时间与公共交货期之差绝对值之和及工件完工时间之和的线性组合的期望值最小 .

问题1|d_j=d|Σw_jT_j的一个全多项式近似方案

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.

具有多重公共工期的单机退化工件排序

研究了需要同时确定最优工件工期和加工序列的单机排序问题。工件的加工时间是其开工时间的线性增长函数。每个工件的惩罚费用包含两部分,一部分是分配给它的工期费用,另一部分是由机器上产生的提前及延迟惩罚费用。管理者的目标为最小化所有工件的总惩罚费用。对于公共工期个数固定的情形,给出了一个多项式时间算法。

最优公共交货期单机提前/拖后调度和对应的批次送货

本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前/拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。

一类具有维护和共同工期的单机排序问题

主要讨论了带有维护和共同工期的单机排序问题.工件的实际加工时间是与该工件在排序中的加工位置相关的.目标函数是共同工期相关的费用、提前完工的工件存储费用和不能在工期内完成的工件的惩罚费用之和.最后给出了多项式动态规划算法.

考虑部分工件不可打扰的多任务调度问题研究

多任务调度问题存在于各种应用领域,如因特网服务领域,医疗领域等。经典的多任务调度模型中所有工件均可被其他等待工件打扰,且仅打扰一次。然而在生产实践过程中,有些紧急工件是不允许被其他工件打扰。在此启发下,对原有模型进行扩展,研究了在单机多任务环境下部分工件不可打扰的调度问题,模型目标包括最小化最大完工时间,最小化总完工时间,最小化最大延迟以及最小化加权提前期、拖延期和共同交货期之和。对于前三个目标给出了精确算法,对于最后一个目标给出了启发式算法。最后,对今后的研究提出了建议。

工件可拒绝与机器具有退化维护活动的无关机排序问题

研究了机器具有退化维护活动和工件可拒绝的无关机排序问题,目标是寻求退化维护活动的位置、接受工件的排序以及每台机器上接受工件的公共交货期,使得所有接受工件的总提前和延误惩罚与所有拒绝工件的总拒绝成本之和达到最小.设计了该问题的多项式时间算法.

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.

公共工期指派和可控处理时间资源约束下最大费用最小化单机排序问题

本文研究具有公共工期指派的凸资源单机排序问题。任务的实际加工时间是所获得的资源量的凸函数,目标函数是所有任务费用中的最大值。考虑两个问题。在第一个问题中,假设可用资源总数量有限,决策者需要寻找任务的最优排序、公共工期和资源分配方案,使得最大费用最小。第二个问题与第一个问题互补,资源总量没有限制,目标是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期及资源分配方案,使得资源总量最小。分别将上述问题转化为非线性凸规划问题加以处理。证明了两个问题均可以在多项式时间内求出最优解,提供了求解上述问题的多项式时间最优算法。分别给出实例说明算法的运算过程和有效性。

多共同工期分配调度问题算法研究

为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。

有公共交货期的单机分批排序问题（英文）

【目的】单机分批排序问题有着广泛的应用背景,很多问题是NP-困难的。有公共交货期的单机分批排序问题是一个非常重要的研究方向。【方法】利用组合最优化的方法,研究工件有公共交货期的最小化误工工件个数和总延误的单机分批排序问题。【结果】对于最小化误工工件个数问题提出了一个多项式时间算法,对于最小化总延误提出了一个伪多项式时间的动态规划算法。【结论】对于其他有公共交货期的分批排序问题的研究提供了重要的研究方法。

带有机器维修和多个工期的单机排序问题

针对具有恶化工件和机器维修的单机排序模型,讨论了多个工期的指派问题。在这一模型中,机器在加工过程中产生恶化使效率降低,工件的实际加工时间是关于开始加工时间的线性递增函数;机器的维修区间是关于开始维修时间的线性递增函数,维修工作完成后,机器将恢复到初始状态,工件的恶化也重新开始。目标是确定最优排序、最优工期和最优维修位置以便极小化工件的提前、延误和工期的总费用。对于这一问题,给出了最优解的一些相关性质,证明了这个问题是多项式时间可解的。

带有资源分配和恶化工件的单机多任务排序问题研究

研究了带有公共交货期的单机多任务排序问题,考虑了两种不同的资源分配函数和位置相关恶化效应函数,目标是找到一个排序和共同的交货期,使得提前、拖期、交货期和资源成本最小,设计了多项式时间算法.针对一个特殊情形,给出了更有效的算法.