摘要
本文首次研究了工件有尺寸大小,有到达时间的分批排序问题,这里目标函数为工件的极大完工时间．就所有工件有两个到达时间的且工件加工时间与尺寸大小一致的排序给出算法,并证明了算法的性能比不超过33/14．
In this paper, we firstly consider the problem of minimizing the maximum completed time on a single batch processing machine if the jobs have different processing times and sizes. We provide an algorithm for the special case in which the lobs have two release times and prove that its worst case ratio is not more than 33/14.
出处
《运筹学学报》
CSCD
北大核心
2006年第4期99-105,共7页
Operations Research Transactions
基金
国家自然科学基金:10671108
山东省自然科学基金:Y2005A04
关键词
运筹学
分批排序
离线算法
性能比
Operations research, batching scheduling, off-line algorithm, wrost case ratio
