订单编组问题的一类特殊模型的有效算法  

Problem of Order Consolidation and Efficient Algorithm for a Special Module

作　　者：王骁力[1] 黄堃[2] 

机构地区：[1]南阳师范学院数学与统计学院,河南南阳473061 [2]平顶山学院数学系,河南平顶山467002

出　　处：《河南科学》2009年第11期1346-1351,共6页Henan Science

基　　金：南阳师院高层次人才科研启动费资助;河南省教育厅自然科学基金资助项目(2009B11017)

摘　　要：工业生产中常遇到按大批量的订单要求加工其所需的产品问题;而把订单要求的一些相同或相似产品合并成批进行批量生产是提高生产效率的一种手段.要考虑的问题是如何分解合并订单使得总的批数达到最大.证明每批的订单总数量均为常数λ的订单合并问题的复杂性,讨论一类特殊的订单合并编组问题并设计其有效算法.The processing according to the prior given orders is often confronted with in industry. And how to consolidate similar product orders to form as many batches as possible is one method of productive efficiency improvement. The problem is to consolidate orders so as to maximize the number of batches. A special case is considered where the orders of only single or a specific pair of products may be grouped in a batch whose size is λ. The problem is proved to be NP-hard in general. A special kind of order consolidation is considered and its efficient algorithm is devised.

关 键 词：订单合并编组 批组 算法复杂性 多项式时间算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O157[自动化与计算机技术—计算机科学与技术]