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

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

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。
     

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

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

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

Two single machine scheduling problems with a learning effect

研究工件具有学习效应的两个单机排序问题.工件的学习效应指的是工件的加工时间为所排位置的函数. 对以下两个目标函数:加权总完工时间与最大延误, 证明在某些特殊情况下加权最小加工时间优先(WSPT)规则和最早工期优先(EDD)规则可以分别给出最优算法. 也给出了这两个规则在一般条件下的最坏情况界.     

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题，目标函数为极小化最大完工时间，总完工时间和加权总完工时间．对于目标函数为极小化最大完工时间和总完工时间的问题，给出了求解最优排序的多项式算法，对于目标函数为加权总完工时间的问题，给出了工件间的一致关系。     

一类单机排序问题的算法研究

本文讨论了加工时间依赖于开工时间的单机排序问题。在这一模型中每个工件具有一个基本加工时间。本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论,对某些特殊情况给出了多项式算法。     

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

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

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

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

误工工件个数和最大费用函数的单机双代理KS公平定价问题

【目的】考虑把资源分配的公平价格问题应用到单机双代理排序中,这里的双代理就是两个代理具有各自的工件集,公平竞争的安排在单台机器上加工自己的工件。【方法】第一个代理的目标函数为在共同工期的前提下最小化总权误工工件个数,第二个代理的目标是为最小化最大费用函数。【结果】给出公平效用的概念和KS公平定价的概念,进而给出了一般情况下KS的价格公平结构性之和紧界分析。【结论】推广了已有文献的结果。     

问题1｜pmtn,d_j｜h_(max)的一个最优算法

研究了具有工期限制、可以中断加工的排序问题１｜ｐｍｔｎ,ｄｊ｜ｈｍａｘ,给出了使最大费用函数ｈｍａｘ＝ｍａｘ｛ｈ１（ｓ１）,…,ｈｎ（ｓｎ）｝最小的一个多项式时间最优算法     

求解多目标单机分批排序问题

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类新型的排序问题．单机分批排序问题就是n个工件在一台机器上加工，要将工件分批，每批最多可以同时加工B个工件，每批的加工时间等于此批工件中的最大的加工时间．目前只有Cheng-shuo Wang，Reha Uzsoy运用Random Key方法编码研究了单目标函数为Lmax的分批排序问题．给出组合优化中的多目标分批排序问题的一种新编码，结合模糊数学知识，运用遗传算法研究多目标分批排序问题．研究了多目标遗传算法的机制特征，进而给出求解多目标分批排序的遗传算法．     

Windows NT操作系统的优先级调度及一种改进方法

首先简要介绍ＷｉｎｄｏｗｓＮＴ操作系统以优先级为基础来安排所有活动的机制,并对其优缺点进行分析．然后针对其局限性,引入一种新的处理器调度方法———处理器继承调度．在此模型中,某些基本线程可作为其它线程的调度者．很多不同的调度策略均可在此框架下得以实现,并且可共存．最后,对于ＷｉｎｄｏｗｓＮＴ操作系统采用此框架的可行性作一定性的讨论,此调度方法的采用将会大大提高系统的灵活性．     

用规则调度方法求解无等待流水车间调度问题

在使用规则调度方法求解无等待最小化总拖期流水车间调度问题时,前提是计算工件的完工时间。提出了计算方法。计算机仿真测试了SPT、LPT、SWPT、EDD、WDD、WPD规则调度方法的性能。结果表明SPT性能最好,SWPT性能最差。     

一种FMS加工中心控制器的实时调度方法

以济南第一机床厂箱体零件的FMS为背景，研究了其底层加工个C的实时调度问题。在综合考虑工件的进料期、交货期和最大生产率等特征之后，提出一种基于批量问题的单机启发式实时调度方法。此方法已在该FMS中应用，且具有广泛的实际应用潜力和理论意义。     

Nachos中基于优先级调度器的实现

Nachos是一个可修改和跟踪的操作系统教学软件,它给出了一个支持多线程和虚拟存储的操作系统框架.Nachos提供的代码框架只有线程结构、SWITCH程序和相关的一些材料.在Nachos代码的基础上,完成先来先服务（FCFS）、非抢占式优先级（PRIO NP）、抢占式优先级（PRIO _P）3种进程调度算法的实现.     

一种特殊的单机双目标分批排序问题

考虑目标函数为Cmax和∑ωjCj的单机上批容量无限制的两类双目标分批排序模型:约束模型和线性加权模型.这里通过动态规划的递推算法分别给出了相应问题的多项式时间算法,并分析了算法的时间复杂性.最后指出在本文约束模型解决前提之下.问题相应的主次指标模型也可相应解决.     

一种基于工作流技术的调度方法

针对传统调度模型在描述复杂生产过程时所面临的模型规模庞大,模型可读性差等问题,提出了一种基于工作流技术的调度模型(WTSM),它通过基于活动的建模并在活动定义中内嵌事件—条件—行为(ECA)规则来达到缩小模型规模,增强模型动态描述能力的目的。同时WTSM定义了独立的资源模型,使之能够更好的支持资源定义以解决资源调度问题。然后采用工作流技术建立相应的调度系统(WTSS),法跟引擎与调度器集成并通过运行模型实例来获得调度方案。实例表明该方法具有模型规模小和调度速度快等优点。     

现场硬实时网络调度算法研究

研究了实时任务死线不大于其周期的任务集调度条件与硬实时网络调度算法约束条件，论证了计算时间复杂度，并将单调死线调度方法直接用于非周期任务调度．最后对调度算法的可调度性进行了严格测试．     

制造型企业生产排产研究综述与展望

通过对大量制造型企业现有排产方法的梳理,综述了当前已有的排产方法,总结了制造型企业排产决策涉及的一般排产问题,比较了各种方法的优劣及适用范围,最后针对现有方法存在的弊端,分析了未来的研究趋势.