“合成链”算法与一类链优先约束的单机分批排序问题  

Composition Chain Algorithm and a Class of Single Batch Machine Scheduling Problem with Chain Precedence Constraints

作　　者：卜宪敏 曹丽霞 刘层层[2] 

机构地区：[1]日照广播电视大学经济贸易系,山东日照276826 [2]曲阜师范大学运筹与管理学院,山东日照276826

出　　处：《洛阳理工学院学报（自然科学版）》2012年第4期79-83,共5页Journal of Luoyang Institute of Science and Technology：Natural Science Edition

基　　金：国家自然科学基金项目(11071142/A011202)

摘　　要：讨论问题1|chains,B|Cmax具体可描述为:有n条链,其中一条链上有n个工件,其余的n-1条链上的工件数之和为常数k,且工件的加工时间不限制,目标函数为最大完工时间。我们对该问题B=2的情况进行了深入的探讨,在研究过程中首次提出"合成链"算法,给出了时间复杂性为O(nk))The issue 1｜chains, B｜ Cmax discussed about in this paper can be described as： When the number of chains is m, the number of parts on one of the chain is n, the sum of the parts on the other m-1 chains is a constant k, the target function will be the maximum completion time on condition that there is no time constraint on the parts processing. This paper has a deep exploration on the B=2 case of this issue, in which it originally presents the Composition Chain Algorithm and works out the polynomial time algorithm with the time complexity O（nk）.

关 键 词：排序 批处理机 链优先约束 算法复杂性 

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