一种特殊的单机双目标分批排序问题  

A Special Single Machine Bi-criteria Batching Scheduling Problem

作　　者：焦峰亮[1] 王磊[1] 张玉忠[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《洛阳大学学报》2007年第4期29-32,共4页Journal of Luoyang University

基　　金：国家自然科学基金资助项目(项目编号:10671108);山东省自然科学基金资助项目(项目编号:Y2005A04)

摘　　要：考虑目标函数为Cmax和∑ωjCj的单机上批容量无限制的两类双目标分批排序模型:约束模型和线性加权模型.这里通过动态规划的递推算法分别给出了相应问题的多项式时间算法,并分析了算法的时间复杂性.最后指出在本文约束模型解决前提之下,问题相应的主次指标模型也可相应解决.Two kinds of bi-criteria models of scheduling n jobs on a single unbounded paraUel-batching machine, which are the constrained model and the linear weighted model, are studied. We mainly concern ∑ωjCj and Cmax, as the objective functions. A corresponding dynamic programming algorithm for each model is and their complexities is analyzed presented. In the end, the constrained model we studied is much more general than the primary-secondary criteria scheduling model is proved.

关 键 词：多目标排序 分批排序 动态规划 

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