时间相关的单机排序的最坏竞争比分析

摘要：

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

关键词：排序、时间相关排序、最坏竞争比、多项式时间算法

所属期刊栏目：30

分类号：O233(控制论、信息论（数学理论）)

资助基金：国家自然科学基金天元专项11226237;重庆市教委自然科学基金KJ120624;重庆师范大学校级资助项目11XLB027, 2011XLZ05

在线出版日期：2013-11-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：5-10