误工工件个数最少的多目标排序问题(英文)  

Multi-criteria Scheduling Problem to Minimize Number of Tardy Jobs

作　　者：陈小林[1] 任子亭[2] 

机构地区：[1]重庆师范大学数学与计算机科学学院,重庆400047 [2]贺州学院计算机科学与工程系,广西贺州542800

出　　处：《重庆工学院学报（自然科学版）》2009年第1期161-164,共4页Journal of Chongqing Institute of Technology

基　　金：重庆市教委科研项目(KJ070802)

摘　　要：考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑Uj为最少,著名的Moore-Hodgson算法得到的排序就是一个可行解,并且该算法在遇到误工工件时总是尽可能把加工时间最长的工件放到误工工件集合L中,这也符合使总完工时间∑Cj为最小的目的.然而以往文献中的例子显示,这样得到的解并不总是最优解,这就暗示了该问题的复杂性,因此给出了不同于以往文献的分支定界算法及其Matlab解,简化了计算过程.The problem of scheduling n jobs on one machine is considered under the multiple objective of minimizing total completion time with the minimum number of tardy jobs. The famous Moore-Hodgson algorithm is used first to determine the minimum number of tardy jobs ∑Uj. The set of tardy jobs L appears to have just the right properties, since Moore-Hodgson algorithm always recommends as the job to join L the largest of a set of jobs, one of which must be tardy. This is in perfect accord with the desire to put longer jobs later, to achieve the minimum total completion time ∑ Cj. However, there exists an example in this paper, which shows that this is not always the optimal set. This hints at the complexity of the problem. So a branch-algorithm that is different from branch-algorithm in this paper and its Maflab solution are presented to produce the optimal schedule, which has significant meaning.

关 键 词：排序 最优性 算法 

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