工件加工可拒绝的无界批量分批排序问题的几点探讨(英文)  

An Unbounded Batch Scheduling with Rejections

作　　者：张咸昭[1] 蔡增霞[1] 任剑锋[2] 

机构地区：[1]临沂师范学院数学系,临沂276005 [2]曲阜师范大学运筹与管理学院,日照276826

出　　处：《运筹学学报》2009年第3期23-30,共8页Operations Research Transactions

摘　　要：本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑w_jT_j+TP和1|B≥n,rej|∑w_jU_j+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.In this paper, we make the study of two batch scheduling problems with rejection 1｜B≥n,rej｜∑ωjTj＋TP and 1｜B≥n,rej｜∑ωjUj＋TP（Here the batch capacity is infinity）. We present pseudo-polynomial time algorithms and fully polynomial time approximation scheme （FPTAS） for the problems under consideration, which are the best known exact and approximation algorithms by far.

关 键 词：运筹学 可拒绝 NP-困难 伪多项式时间 FPTAS 

分 类 号：O223[理学—运筹学与控制论] TP301.6[理学—数学]