带有公共交货期窗口问询和退化工件的单机排序问题

为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差异化的退化因子;工件的实际加工时间与其开始加工时间、退化因子呈线性关系。分析了交货期窗口决策和工件排序具有的最优性质,以及最优的工件排序与工件退化因子之间的关系,并提出了最优算法。研究表明:可基于工件的退化因子确定最优工件加工顺序,最优交货期窗口的开始时间和结束时间分别对应于最优序中某个工件的完工时间,研究问题可在多项式时间内进行求解。

基于单机排序问题的降落飞机分组排序方法

为使单跑道降落飞机排序结果在实际操作时可行、简单,首先限制同一航路段上的飞机按照先来先服务的原则排序,在最终的排序中,其拓扑次序不变;其次提出了将飞机分组排序的思想,对同一航路段上刚好满足最小安全间隔的飞机做为一个飞机组参与排序。使用1|chains|∑wjcj做为排序模型,通过求解各飞机链的ρ因子可以快速得到排序结果。将本方法用于对双流国际机场和其它几个机场的实际航迹数据进行计算,得到的排序序列完全符合实际管制需要,具有很高的推广应用价值。

一致条件下具学习因子的几个单机排序问题(英文)

n个工件需在同台机器上依次加工,工件j,j=1,2,…,n所需的正常加工时间为pj,如在某序中工件j第r个加工,则机器对其实际加工的时间为Pjrα,其中α≤0为一学习因子.要求适当排列这n个工件的加工顺序,使某目标函数达最小.本文对加权完工时间之和,最大迟后,延误工件数这三个目标函数,给出了在相应的一致条件下,对应的WSPT规则,EDD规则,修正Moore-Hodgson算法可获最优序,并估计了在一般情况下由该三规则所获序的误差.

单机排序问题|r_j,prmp| ∑w_j(1-e^(-ac_j)) 的动态在线调度

本文首先一般化了可中断的概念,并建立了相应的中断—安装重复模型,然后研究了单机排序问题1|rj,prmp| wj(1-e-acj)在中断—重复和中断—安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则。

单机排序问题的数学规划表示

本文把单机排序问题 １‖∑ｗｊＣｊ表述成一个二次规划，并把不带权的问题１‖∑Ｃｊ进一步转化成指派问题，从而用指派问题的匈牙利算法证明 ＳＰＴ序是问题１‖∑Ｃｊ的最优解．这个结论似乎很平凡，但对于用数学规划来研究排序问题是一个很有意义的进展．这为我们用二次规划和半定规划来研究ＮＰ困难的排序问题的近似算法打下基础．

单机排序元胞传输模型在终端区排序中的应用

为缓解终端区航班延误问题,将终端区进场航空器排序过程分为航路飞行排序阶段和汇聚排序阶段,从而降低问题复杂度,结合单机排序算法与元胞传输理论,利用标准雷达引导航线,并结合实际管制经验,建立以系统运行时间最短为目标函数的元胞传输模型;根据航空器对链一体化原则,将等待着陆的航空器分组,并赋予相应的权值,针对航空器对链影响因子的不同进行排序,并结合实例计算得到系统总运行时间,起点处等待时间,最终着陆顺序等。结果分析表明,该优化模型能够反映终端区进场航班的动态特性,给出合理的航空器进场顺序,为终端区进场航班提供路径参考,满足实际的运行需求。

在退化维修下带有工期指派和加工时间可控的单机排序问题

讨论在一次退化维修下带有3种工期指派和加工时间可控的单机排序问题。其中机器的维修时间是维修开始时间的线性非减函数,工期指派的3种模型包括共同工期指派模型、松弛工期指派模型、无限制工期指派模型,工件的实际加工时间依赖于工件的开工时间、工件的位置以及资源分配的函数。目标是要找到机器的最优维修位置和最优排序,极小化提前时间、延误时间、工期以及资源分配的总费用。当机器的维修位置固定时,证明了该问题可以转化为指派问题;当机器的维修位置不固定时,给出了一个算法,并证明了该问题可以在O(n4)时间内求得最优解;最后以共同工期指派模型为例给出一个实例。

到达时间依赖于资源分配的单机排序问题

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。

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

讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序。

基于一般学习效应下的单机排序问题(英文)

近来具有学习效应的机器排序问题收到广泛的关注.对于机器排序中工件的实际加工来说,与工件加工位置有关的学习模型更具有现实性.本文研究了工件加工位置和与已经加工过的工件之和有关的一般学习效应模型.首先证明文献中与位置和已经加工过的工件加工时间之和有关的学习模型是本模型的特殊情形.其次对于单机排序问题我们提出一般解法.

关于具有主次指标的单机排序的注记

本文讨论具有主次指标的单机同工期排序问题,其主指标和次指标取为:最大误时、总流程、误时工件数、总误时、加权总流程、加权误时工件数以及加权总误时。

任务到达时间依赖资源的单机排序问题

讨论了任务到达时间依赖于分配给它的资源的一类资源约束问题 ,对问题 1 |rj=fj(uj) , nj=1uj≤U∧|Cmax,将已有的一个算法做了改进 ,对问题 1 |rj=fj(uj) ,Cmax≤C∧|Σuj

关于最小化总误时单机排序问题的若干注记

最小化总误时的单机排序问题是一个著名的复杂性迄今未知的问题,人们曾作了大量的研究.本文在前人工作的基础上,对一种特殊情况(诸工件的工时与工期有同序关系的情况)给出了一个简单解法.对一般情况改进了最优解的必要条件和已有的消去规则.

具有学习效应和遗忘效应的间歇批生产的单机排序问题

本文研究具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题,考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递的三种模型.对目标函数为最大完工时间的情形,指出机器在批与批之间没有学习效应的传递和有部分学习效应传递的情形下是多项式可解的,并进一步对机器在批与批之间有总的学习效应传递的两种特殊情形给出了多项式时间算法.

带有安装时间与维修活动的单机排序问题

考虑带有安装时间与维修活动的单机排序问题。每个工件都有自己的交货期窗口,工件在交货期窗口之前或之后完成都会产生费用。工件在加工之前需要安装时间,安装时间为加工时间的线性函数。维修活动使工件的加工时间缩短,并且维修活动的长度可以通过资源分配减少,考虑维修活动的2种情况:维修活动的长度与已完成工件的加工时间有关;维修活动的长度与维修的位置有关。在维修活动的2种情况下,根据维修活动的不同位置分类讨论,目标是找到交货期窗口的大小和位置,以及带有资源的维修的位置,使得提前费用、延误费用、交货期窗口的位置和长度产生的费用与资源的费用之和最小。证明了该问题在多项式时间内是可解的。

带有拒绝、恶化效应和安装时间的单机排序

研究带有安装时间、工件加工时间具有恶化效应及工件可拒绝的单机排序问题。工件的安装时间依赖于已完工工件的加工时间总和,且工件的加工时间同时受到双重恶化效应的影响。工厂可以拒绝加工工件,因而将工件分为接受与拒绝工件集,拒绝工件需要支付拒绝惩罚。目的是确定接受工件的集合、拒绝工件的集合以及接受工件集合中工件的最优排序,分别使最大完工时间、总完工时间、总完工时间的绝对差以及总等待时间的绝对差与总拒绝惩罚之和最小。将上述4个目标函数对应的问题分别转化为指派问题进行求解,给出了一个多项式时间算法,并证明了其时间复杂度。利用数值算例进行了验证,说明给出的求解算法有效。

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

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

最小化总误时的随机型单机排序问题

本文研究最小化总误时的随机型(即工件的加工时间为随机变量)排序问题,推广了[1—2]的主要结果。

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题.在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,首先考虑了问题的可行性.通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法.对于可行问题,给出了一个算法在多项式时间内获得最优排序.

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

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