加工时间为线性增函数有上界的排序问题

摘要：

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1∣pj(t)(t0, T1, T2)∣Cmax:设工件集J ={J1, J2,...,Jn}中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻 t0>0开始加工;Ω1中工件的加工时间为pj(t)=ajt1(当t≥T1),Ω2中工件的加工时间为Pj(t)=ajt(当t<T2)或Pj(t)=ajT2(当t≥T2)，其中T2>T1>t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cmax.在所得的引理2和引理3的基础上,本文给出一个复杂度为n log n的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的.

关键词：排序、加工时间增加、最大完工时间

所属期刊栏目：27

分类号：O223(运筹学)

资助基金：国家自然科学基金10871143

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

页数：共6页

页码：1-6