带有交货期窗口和加工时间可控的排序问题

讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。     

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

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

具有学习效应和非线性安装时间的单机排序问题

讨论了加工工件具有学习效应和安装时间的单机排序问题。文中工件的加工时间不是固定不变的,不仅与工件的加工位置有关,同时还与已加工完成工件的加工时间有关。安装时间分为线性安装时间和非线性安装时间,本文主要讨论的是具有非线性安装时间的情况。工件的安装时间是依赖于已加工完的工件的实际加工时间和工件所排列位置的函数形式。在文中主要证明了极小化最大完工时间,极小化完工时间总和问题是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误问题是多项式可解的。     

带有交货期和加工时间可控的单机排序问题

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

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

带有学习效应和机器可用性限制的排序问题

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。     

LS排序的界

讨论任务的加工是不可中断,处理机是同速机的排序问题Ｐｍ,ａｉ∥Ｃｍａｘ,证明了用ＬＳ算法求解该问题的误差界是２－１／ｍ。     

处理机具有准备时间的变速机排序问题Rm,a_i｜｜∑C_j

讨论任务加工不可中断,处理机为变速机的排序问题Ｒｍ,ａｉ｜｜∑Ｃｊ．通过改变加工时间矩阵,将其转化为经典排序问题求解     

一类资源约束单机排序问题

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

带有交货期窗口和工件可拒绝的单机排序问题

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。