在传统的在线排序模型中,人们大多数考虑单个目标的在线排序.然而,随着当今时代的发展,单个目标往往不能满足工业生产的需求.本篇论文研究了双指标在线排序问题.工件是在m台平行批机器上加工.在线即为工件在线到达,工件的到达时间记为rj.工件的所有信息包括加工长度pj、加工费用(工件Jj在机器Mj上加工产生的费用)Cij、运输时间qj等是直到到达后才知道.本文考虑的工件长度都相等.平行批机器批次中的容量分为无界(b=∞)和有界(b<∞)两种情形.批次的长度等于最长工件长度.工件Jj在机器Mj上加工产生完工时间Cj、费用Cij,1 ≤ j ≤ n,1 ≤ i ≤ m.本文中双指标在线排序问题包括两种目标函数一致最优和两种目标函数分层最优两类.其中模型中包含的单个目标函数如下:时间表长Cmax＝maxj Cj、总加权完工时间∑wjCj、最大交付完工时间 Dmax=maxj{Cj+qj}、最大流程时间Fmax=maxj{Cj-rj}、以及最大机器费用MMC(Maximum Machine Cost)即所有机器费用中的最大者.第二章讨论了 m台平行批机器上最小化时间表长及总加权完工时间一致最优的在线排序.本章考虑了机器批容量无界的情形.给出了使得两目标函数一致最优的最好可能的在线算法,算法的竞争比为1+αm,αm满足(1+αm)m+1=αm+2.第三章讨论了 m台平行批机器上最小化时间表长及最大交付完工时间的一致最优的在线排序.本章考虑了机器批容量无界的情形.给出了竞争比为1+βm的最好可能的在线算法,βm满足(1+βm)m+1=2+βm.第四章讨论了 m台平行批机器上最小化时间表长及最大流程时间的一致最优的在线排序.本章考虑了机器批容量有界的情形.给出了竞争比为1+α的最好可能的在线算法,α=(?).第五章讨论了 m台平行批机器上最小化时间表长及最大流程时间的分层最优的在线排序.目标是在最大流程时间最优的前提下使得时间表长最优.本章考虑了批容量无界的情形.给出了竞争比为(1+αm,1+mαm+1/αm2+2αm)的最好可能的在线算法,其中αm满足α2+(m+1)α-1=0.第六章讨论了 m台平行批机器上最小化时间表长及最大机器费用的分层最优的在线排序.目标是在时间表长最优的前提下使得最大机器费用最小.本章考虑了机器批容量无界的情形.给出了竞争比为(1+βm,(?))的最好可能的在线算法,其中βm 满足(1+βm)m+1=βm+2.