误工排序问题的研究

误工排序问题是经典排序论中最基本和最重要的问题。40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现。本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义。这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果。

一类自由作业供应链排序的研究

本文研究一类集成工件生产和发送的排序模型。在该模型中,供应链的上游首先将工件安排在自由作业机器上加工,然后把加工完毕的工件分批发送给下游。问题是寻找生产和发送相连的排序,使得生产排序费用和发送费用总和最少。这里,生产排序费用是以工件带权送到时间和表示;发送费用由固定费用和与运输路径有关的变化费用组成。在指出问题的NP困难性后,本文用动态规划算法构造了一致条件下的多项式时间近似算法,并分析算法的性能比。本文最后还讨论了该问题的其它情形。

单纯形法解装卸工问题

本文提出装卸工问题,对一种特殊情况下的装卸工问题用单纯形方法求得了它的最优解和最优值.

Moore-Hodgson算法最优性的新证明

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O(nlogn)内得到误工问题的最优解。虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂。本文给出Moore-Hodgson算法最优性的一个非常简洁的新的证明。由于误工问题在排序论里的重要性,本文给出的新的证明在理论上是有重要意义的,是可以为排序论的专著和教材所采纳的。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,也可能有简洁的证明。

平行机及自由作业的排序与转包

研究工件排序与转包相联的模型,即制造商从客户处接受一批工件,这些工件既可以由制造商加工,也可以一定费用转包给承包商加工.制造商需要确定被转包的工件集及工件的加工顺序,使得加工费用和转包费用之和为最小.研究制造商为平行机及自由作业,承包商为单机情况下的排序与转包模型,基于动态规划算法给出了近似算法,并分析了该算法的性能比.

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

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

同类机的供应链排序

研究同类机环境的供应链排序,即研究如何安排工件在同类机器上加工,把加工完毕的工件分批发送给下游客户,使得生产排序费用和发送费用总和最少.生产排序费用是用工件送货时间的函数表示,发送费用是由固定费用和与送货路径有关的变化费用组成.研究以工件最大送货时间和平均送货时间为生产排序费用的不同目标函数下的同类机供应链排序问题,用动态规划算法构造了多项式时间近似算法,并分析算法的性能比.

带时间窗分车运输同时收发车辆路径问题及其启发式算法

本文结合汽车零部件第三方物流的实际背景,提出了带时间窗的可分车运输同时收发车辆路径问题(简称SVRPSPDTW),并给出了问题的数学模型,同时提出两个求解该问题的启发式算法,最后进行了数值试验。由于没有可以利用的算例,本文在Solomn测试基准库的基础上构建了针对新问题的算例。计算结果表明,所有算例计算时间均不超过1秒,且算法1无论是从车辆的使用数还是从车辆行驶的路径总长度上都明显优于算法2,从而说明算法1是寻找SVRPSPDTW问题初始可行解的较为有效的算法。

与交货期有关的供应链排序问题

本文在供应链中把多制造商、多客户的生产和运输集成起来研究,解决工件带有交货期的供应链排序问题.以生产和运输的总费用达到最小作为目标,建立问题的集成排序模型,在分析解的最优性条件基础上,分别用工件的最大延迟和误工工件数作为排序目标,给出相应的动态规划算法,并分析算法的复杂性.

一类新的车辆路径问题及其两阶段算法(英文)

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法:两阶段算法.最后在改进的Solomn的算例的基础上,进行了数值试验.

自由作业环境下的供应链排序

本文研究了一类集成工件加工和发送的供应链排序模型.利用排序理论和动态规划方法,获得了两机器情形下的供应链排序问题的多项式时间近似算法,并证明算法的性能比为2.

转包且具有不同费用时间段的排序问题（英文）

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.

KIM算法的最优性

研究工件的就绪时间可以不相同、但是与交货期有"一致性"关系的误工问题.1978年Kise,Ibaraki,Mine提出算法(简称为KIM算法),证明他们提出的KIM算法可以得到这个误工问题的最优解.最近李杉林、陈志龙、唐国春用反例指出Kise,Ibaraki,Mine证明最优性时提出的引理2是错误的,并用新的方法证明KIM算法的最优性.越民义则给出一个非常简洁的证明.本文分析引理2的错误所在,给出修改后的引理2’,由此似乎应该相应修改KIM算法,然而我们证明原来的KIM算法仍然可以得到最优解.

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

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

分车收发车辆路径问题的三个启发式算法之比较

车辆路径问题已经出现了很多的变种.在这些扩展的VRP问题当中,分车收发车辆路径问题就是其中之一.本文针对这一问题在已有的模型上加以改进,并且提出了摆脱车辆数限制的最远点拼车算法和竞争决策算法。最后结合最远点完全拼车算法通过数值实验对三者进行了比较.结果显示竞争决策算法得到的结果好于其他两者,其次是最远点拼车算法。

最大完工时间排序的两人合作博弈

在现实世界中,往往存在一方无法承担一个项目中全部工件加工任务的情况。这就要考虑由两方合作共同完成任务,每一方都有一台机器用于加工工件的情形。双方通过协商,确定这批工件的一个划分,把工件分配给这两台机器,使得相应的合作(加工)收益分配合理,能够被双方接受。研究了加工工件都相同的情况下,由最小的最大完工时间作为加工成本的两人合作博弈问题。

单机供应链排序及流水作业的反问题模型

最优化问题是在给定参数情况下,对某个目标函数,如费用、容量等,寻找问题的最优解。然而在许多现实生活中,有时只能知道问题的参数近似值和一个可行解,需要最小程度地调整参数,使得给定的可行解成为最优,这就是最优化问题的反问题。本文研究单台机器供应链排序和流水作业排序的反问题。根据调整参数的不同,本文利用排序理论把这些反问题表示为相应的数学规划形式。

现代物流技术中装卸工问题的拟多项式时间可解情况

装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展,促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题,本文研究限制情形下的装卸工问题,并证明是拟多项式时间可解的。

关于Scheduling中文译名的注记

Scheduling是运筹学和组合最优化的一个分支。国际上,Scheduling发展已经有50年。1960年,越民义编写国内第1本排序理论讲义至今也有半个世纪。Scheduling的理论和应用涉及到数学、管理、自动化、系统工程和工业工程等许多学科。回顾和比较国内外使用排序、调度等Scheduling中文译名的情况,介绍新近提出的排序与调度译法,建议在泛指Scheduling时,采用该译名。

单台机器总完工时间排序问题的反问题

运筹学和最优化的种种问题(“正问题”)是在已知各有关参数或者数据的条件下,找出最优(最快、成本最省或者效益最大)的方案.所谓的“反问题”,是指已经有一个方案,但在目前的情况下,该方案并非最优,需要考虑如何最小限度地改变现有参数,使这个方案成为最优的方案.如果说“正问题”的研究有助于一个新系统的设计和确定,那么“反问题”的研究对改善现有系统的性能具有重要的意义.本文以数学规划为工具。