论文部分内容阅读
多目标排序是研究多个优化目标的排序问题，在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。2007年有文献证明以误工工件个数最少为第l目标、使总完工时间最小或者使总延误最小的多重目标排序问题1‖（∑Cj／∑uj）或者1‖（∑Tj／∑Uj）都是NP困难的。然而，迄今为止，对于以误工工件个数最少为第1目标、使最大延误最小的多重目标排序问题1‖（Tmax／∑Uj）的计算复杂性还不清楚。给出了这个多重目标排序问题1‖（Tmax/／∑Uj）的分支定界算法，借助几个性质，得到较好的上下界，