分批排序问题1|B,r_j,s_j|L_(max)的近似算法

作     者：陈俊 吴翠连 CHEN Jun;WU Cui-lian

作者机构：泰山职业技术学院信息工程系泰安市271000 曲阜师范大学管理学院山东省日照市276826 

基　　金：国家自然科学基金资助项目(11071142) 

出 版 物：《曲阜师范大学学报（自然科学版）》 (Journal of Qufu Normal University(Natural Science))

年 卷 期：2012年第38卷第2期

页      码：54-57页

摘      要：主要讨论了工件有到达时间、加工时间和尺寸的目标函数是极小化最大延误时间的单机分批排序问题1|B,rj,sj|Lmax.在机器容量B为常数时,即使在B=2和工件的到达时间与尺寸都相同时,问题也是强NP—难的.基于问题1|B,rj|Lmax目前最好的多项式时间近似算法——PTAS算法(从算法的最差性能比来说是最好的),我们采用任意工件可以按尺寸拆分的技巧,针对问题1|B,rj,sj|Lmax设计了一个多项式时间的近似算法,并分析出这个算法的最差性能比为2+ε(其中ε是任意小的正数).

主 题 词：分批排序 最大延误时间 最差性能比 近似算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.3969/j.issn.1001-5337.2012.02.011

馆 藏 号：203510936...