论文部分内容阅读
生产计划管理中的一个非常重要的问题就是如何充分利用有限的资源去完成预定生产计划使得预期的目标达到理想或最优,其中的众多问题可以描述为排序模型.当有多个指标需要综合考虑时,寻求所有Pareto最优点及其相应的Pareto最优排序则是解决问题的理想模式.此时称所研究的问题为Pareto最优排序问题.我们将单机上带有限制条件β同时最小化两个目标函数f和g的Pareto最优排序问题记为1|β|(f,g),β表示位置限制条件或add假设.其中位置限制条件ρ(Ji)≤ki表示工件Jj只能在σ中前kj个位置进行加工；add假设表示将n个给定的工期按照任意顺序分配给工件.给定可行排序π,若不存在其他可行排序σ使得f(σ)≤f(π),g(σ)≤g(π),并且这两个不等式至少有一个严格成立,则称π是一个Pareto最优排序,并称(f(π),g(π))是相应于排序π的Pareto最优点Pareto最优排序问题的目标是找出所有的Pareto最优点,并对每一个Pareto最优点找出一个相应的Pareto最优排序.本文研究了单机上的下述Pareto最优排序问题：·在位置限制下单位长度工件单代理Pareto最优排序问题1|σ(Ji)≤ki,pi=1| (∑i=1n Ui,fmax);·在add假设下单代理Pareto最优排序问题1|add|(∑i=1n Ui,fmax);·在B-工件位置限制下单位长度A-工.件两个代理Pareto最优排序问题1|σ(JjB)≤ kjB,piA=1 |(∑i=1nA UiA,fmaxB);·在add(A)段设下两个代理Pareto最优排序问题1|add(A)|(∑i=1nA UiA,fmaxB).·在add(B)假设下两个代理Pareto最优排序问题1 |add(B)|(fmaxA,LmaxB).本文的主要结果如下：·问题1 |σ(Ji)≤ki,pi=1 |(∑i=1nUi,fmax)在O(n4)时间内可解.·问题1 | add|(∑i=1nUi,fmax)在(n3)时间内可解.·问题1 |σ(JjB)≤kjB,piA=1|(∑i=1nAUiA,fmaxB)在O(n2nA)时间内可解.·问题1 | add(A)|(∑i=1nAUiA,fmaxB)在O(n2nA)时间内可解·问题1 | add(B)|(fmaxA,LmaxB)在O(nnA2nB+nAn2B lognB)时间内可解.