时间相关的单机排序的最坏竞争比分析 (运筹学与控制论)

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。     

供应链排序中的外包问题 (运筹学与控制论)

为了更好地将供应链排序和现实生活结合以体现其应用价值,文章研究了一类可以外包的供应链排序模型。外包即指为了提升效率,节省总费用,而采取将工件由其它制造商代替加工的现象。所有的工件均可以在制造商内部加工也可以进行外包加工,外包工件加工完成后必须分批运回制造商才算完工。所研究的模型中有一个制造商和一个外包商,制造商的加工环境为m台平行机,外包商为单台机器。因此在模型中要考虑外包费用、运输延迟以及运输费用,所要做的就是确定外包工件以及工件的加工顺序和外包工件的配送顺序。对于该问题,本文主要研究了目标函数分别为总完工时间、最大延迟以及误工总数的情形;分析了问题的复杂性,运用动态规划的技巧给出了最优算法且分析了算法的时间复杂性。     

一类带有可控加工时间的单机排序问题 (运筹学与控制论)

讨论了具有学习效应的工期指派和可控加工时间的单机排序问题。工件的实际加工时间同时依赖于所排位置和所分配的资源消耗相关的函数,资源消耗分为线性和凸资源消耗2种。考虑共同工期、松弛工期和没有限制的工期3种工期分派方法。目标是确定工件最优的加工顺序、工期和资源分配量,极小化一个包含提前、延误、工期分派、总完工时间和总资源消耗的总费用函数。对于上述2种不同资源消耗函数与3种不同的工期分派方法的每一种组合,均给出了多项式时间算法。     

工件具有指数学习效应的流水作业排序问题

讨论了工件具有学习效应的流水作业排序问题.目标函数为极小化最大完工时间和极小化总完工时间和.利用Gonzalez和Sahni提出的STPT算法规则估计了此两目标函数的最坏情况界,同时举例说明了对于两台机器流水作业的Johnson规则对于本研究问题并不适用.另外,对所讨论的问题的一些特殊情况分别给出了多项式时间算法.     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为 0.4117 ,分支定界算法的效率比较高,处理 100 个工件所用的最大时间不超过 460s 。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。
     

排序博弈:合作博弈的新发展 (运筹学与控制论)

本文指出人类社会发展模式的巨变决定合作博弈理论研究和应用研究的必要性和紧迫性;简要综述以合作联盟内的任务分配不是决策变量为特征的合作博弈模型的研究成果;系统介绍由Nash(纳什)创立的把联盟内的任务分配作为决策变量的另一类两人合作Nash Bargaining Model(NBM,纳什博弈模型)及其Nash Bargaining Solution(NBS,纳什博弈解);强调排序博弈是NBM在管理学中的离散化发展;完整介绍此离散化方面开创性论文中全新的定义、改进的博弈模型、创新的博弈机制、求解博弈解(集)的精确算法;最后指出NBM的改进和离散化这两方面后续研究的几个重要方向。     

带有公共交货期窗口和加工时间可控的单机排序问题 (运筹学与控制论)

讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题。假设工件的加工时间是所分配资源的线性非增函数,且分配资源会产生费用。交货期窗口的开始时间是固定且不受限制的,交货期窗口的结束时间是不确定的决策变量(即交货期窗口的大小不确定)。如果工件在窗口中完工则不产生费用,否则工件提前或延误,则会产生相应的提前或延误的费用。目标函数是极小化总完工时间,提前时间,延误时间,交货期窗口的结束时间(即窗口的开始时间与窗口大小的和)和资源分配的总费用。给出了最优解的一些性质,并且证明了这个问题是多项式时间可解的。     

带有交货期和加工时间可控的单机排序问 (运筹学与控制论)

讨论了带有交货期和工件的加工时间可控的单机排序问题。本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序。然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的。最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nl ogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序。     

排序论基本概念综述 (运筹学与控制论)

第二次世界大战期间运筹学(Operations research)兴起,首次把运作(Operation)作为研究对象。研究运作的时间安排又促成排序(Scheduling)概念的建立和研究的开展。经过50多年的发展,国内排序术语正在逐步走向统一,这是学科正在成熟的标志,也是学术交流的需要。王元院士等于2010年8月编辑出版的《数学大辞典》是一部综合性的数学大辞典,目前正在修订出版第2版。中国运筹学会排序专业委员会(排序分会)组织34位专家执笔和审阅了39条排序论最基本的概念,供入选《数学大辞典》第2版用。本文综述了这39条排序论最基本的概念,旨在征求意见,为以后编辑出版完整的《排序论辞典》奠定基础。     

排序论中工件和机器的对偶性 (运筹学与控制论)

提出排序问题中工件和机器的对等性,定义排序问题的对等排序,列举单台机器排序问题和多台机器自由作业排序问题的对等排序;在此基础上,把工件和机器看成是对偶的双方,研究这两者的对偶性,进而提出排序问题的对偶排序;研究排序问题与其对偶排序之间的关系——对偶关系,可能是排序论研究的新方向。     

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

本文研究了目标函数为总完工时间,具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题.考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递3种模型.首先,在批与批之间没有学习效应传递的模型中,给出了复杂性为O(nlog n)的最优算法.其次,在批与批之间有部分学习效应传递的情形下,对批在...     

带凸资源依赖的一类单机排序问题

就工件的实际加工时间是之前已加工工件的正常加工时间和的指数学习效应且具有凸资源依赖的单机排序问题展开讨论。在所有工件的正常加工时间均相同的假设下,对最小化加工全程和资源消耗总费用的和、最小化完工时间和资源消耗总费用的和,最小化总提前、总延误、总共同交货期和资源消耗总费用的函数以及最小化总提前、总延误、总松弛交货期和资源消耗总费用的函数四个目标函数分别给出了多项式时间可求解的算法。
     

时间错位和序列错位呈线性关系的重新排序 (三峡地区资源环境生态研究)

讨论了时间错位和序列错位呈线性关系,即最大时间错位与最大序列错位之和、最大时间错位与总序列错位之和、总时间错位与最大序列错位之和、总时间错位与总序列错位之和限制下,以使总完工时间最小为目标的重新排序问题。重新排序就是原始工件已经按照某种规则使目标函数值达到了最优,但还没有开始加工,这时又有一批新工件到达,要求将新工件与原始工件一起重排使目标函数为最优的排序问题。根据经典排序理论,证明了原始工件与新工件按最短加工时间优先规则可以使目标函数达到最优。由动态规划原理,对每个问题设计并证明了不同的算法及其时间复杂性,最后结合实例作了进一步论证。     

重新排序问题的Pareto最优解

为了保证先来顾客的需求和工件本身错位量的要求,着重研究这种使先来顾客的总目标函数值与工件错位量之间达到平衡的问题,即重新排序问题的Pareto最优解问题.对于最大延迟和工件错位量的Pareto最优解问题,给出了这些问题的多项式时间算法或计算复杂度.     

带有学习效应的多客户配送的供应链排序问题

针对机器具有学习效应,且需要多客户配送的供应链排序模型。在这一模型中,机器上工件加工时学习效应会发生,工件的实际加工时间是与其位置相关的减函数。客户需要接纳与其对应的完工工件,每一批次的工件完工后完需要配送,然而配送都会花费一些时间以及费用。由于需要配送的大量客户,为了尽量节约资源,减少车次数量以及运输次数,所以运输车辆都要尽可能多的装载货物才开始运输。在针对一台运输车辆内装载有不超过两个客户的工件情况,研究的目标函数为极小化总流程时间和极小化最大延迟时间,并对这两个问题分别给出了相应的动态规划算法。
     

重新排序中目标函数与错位量的Pareto最优解

基于ε-约束的方法,研究了重新排序中目标函数与错位量的Pareto最优解问题,对于总完工时间或最大完工时间与时间错位量或序列错位量的Pareto最优解问题,本文给出了这些问题的多项式或拟多项式时间的算法.     

一类具有学习效果的单机排序问题

讨论一类具有学习效果的单机排序问题.在这类问题中,由于学习效果的作用,工件加工时间将逐渐减少.学习效果通过工件正常加工时间的分段线性函数来描述.基于对问题的分析,把目标函数为极小化总惩罚的工期确定问题转化成指派问题,从而得到问题的多项式算法.对于极小化完工时间和与完工时间偏差的双目标问题,其一般情况同样可以转化成指派问题.此外,对于某些特殊情况,给出了极小化最大完工时间问题与完工时间和问题的简便算法.     

具有固定顺序的重新排序问题

在生产实际中经常会出现顾客订单不同时到达的情况,为了保证先来顾客的需求和工件本身的要求,往往是先安排好的工件保持相对顺序不变,使其与后来顾客的工件重新排序.本文着重研究了这种使先来顾客的工件保持相对固定顺序,在有限错位限制的条件下使总目标函数值最优的重新排序问题。     

同时具有学习和恶化效应的单机成组排序问题

讨论了一类工件的加工时间具有学习效应且安装时间带有恶化的成组排序问题,目标函数分别为极小化最大完工时间和极小化总完工时间,1｜pij=aij-bijt,S=δit,GT｜Cmax,1｜pij=aij-bijt,S=δit,GT｜∑Cij,并分别给出了求最优解的多项式时间算法,其中极小化总完工时间问题是在bij=b,δi=δ的特殊情况下给出的。