在误工工件个数最少的条件下使最大延误为最小的分支定界算法  

A Branch-Bound Algorithm to Minimize the Maximum Tardiness with Minimum Number Tardy

作　　者：董柳毅[1] 陈小林[1] 唐国春[1,2] 

机构地区：[1]重庆师范大学数学与计算机科学学院,重庆400047 [2]上海第二工业大学管理工程研究所,上海200041

出　　处：《上海第二工业大学学报》2008年第4期286-290,共5页Journal of Shanghai Polytechnic University

基　　金：国家自然科学基金项目(20710015);运筹学与系统工程重庆市市级重点实验室资助

摘　　要：多目标排序是研究多个优化目标的排序问题,在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。2007年有文献证明以误工工件个数最少为第1目标、使总完工时间最小或者使总延误最小的多重目标排序问题1‖(∑C_j/∑U_j)或者1‖(∑T_j/∑U_j)都是NP困难的。然而,迄今为止,对于以误工工件个数最少为第1目标、使最大延误最小的多重目标排序问题1‖(T_(max)/∑U_j)的计算复杂性还不清楚。给出了这个多重目标排序问题1‖(T_(max)/∑U_j)的分支定界算法,借助几个性质,得到较好的上下界,能够较快地得到最优解。Multi-criteria scheduling problems play more and more important roles in solving complicated problems appearing in economy, management, engineering, military affairs and society etc. In 2007, a paper proved that the two multi-criteria scheduling problems 1‖（∑Cj/∑uj） or 1‖（∑Tf/∑uj） to minimize the total completion time or the total tardiness with minimum number of tardy jobs are NP hard. However, till now, the computational complexity of the multi-criteria scheduling problem 1‖（Tmax/∑Uj） have still not been known. In this paper, the authors propose a branch-bound algorithm for the problem l1‖（Tmax/∑Uj）. They find its several properties. Through them, they get good upper and lower bounds, and so get the optimal solution more quickly.

关 键 词：排序 延误 算法 

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