论文摘要
多目标排序是研究多个优化目标的排序问题,它在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。以往对单台机器排序问题的研究大都限于单目标排序,追求某一个目标的优化时往往以劣化其他目标为代价。然而在实际的生产调度和计划管理中,绝大多数情况需要综合考虑一个作业排序的许多性能指标,即需要求解多个目标函数的最优或近似最优加工顺序或在某目标函数约束范围下求其它一些函数的最优或近似最优解的排序。如果研究这些问题提出他们的解决方案,并进一步有效地、恰当地将这种方法应用于经济、管理、工程及社会相关领域,那么对于提高生产率、增加利润、扩大生产都是非常有益的。当γ1和γ2∈{Tmax,∑Cj,∑wjCj,∑Tj,∑wjTj,∑Uj,∑wjUj},可以提出P72=42个不同的多重目标排序问题,对应有42个约束多目标排序问题。本文着力研究了其中的7个约束解问题,相应问题的多重解可视为约束解的一种特例。第一章:综述了排序的研究意义与研究现状;引入排序问题的常用参数及记号;介绍了单机多目标排序问题的已知结果。第二章:针对在实际问题中往往是允许工件误工的,也就是说,工件可以在交货期之后完工,即允许工件有延迟或者延误,只是对于不同的问题对工件的延迟或者延误有不同的要求。本章节研究以延迟和延误为第1目标的四个约束多目标排序问题,在最大延迟Lmax、总延迟∑Lj、最大延误Tmax或者总延误∑Tj不超过给定的量的约束条件下,寻找使平均完工时间为最小的排序,给出前三个问题相应的最优算法,由于最后一个问题是NP难题,本文提出了分支定界算法、启发式算法及其加速搜索的方法,并找到了启发式算法为最优时,工件的加工时间和交货期之间必须满足的条件。第三章:考虑n个工件在单台机器上加工在误工工件个数少于某个确定数的条件下使总完工时间（或平均完工时间）最小的多目标排序问题,即问题1‖（∑Cj/∑Uj≤k）。首先,对于某些工件必须不误工使总完工时间（平均完工时间）为最小排序问题,提出简单的算法。与Moore算法结合利用简单的启发式方法,给出分支定界算法,借助优势规则删掉许多分支,能够有效地得到最优解。第四章:本章节研究了以总完工时间为第一目标的两个约束多目标排序问题,在总完工时间不超过给定量的约束条件下,寻找使带权完工时间或最大延误为最小的排序,分别给出了相应的启发式算法和分支定界算法;