并行分批在线排序问题和排序博弈问题的研究

摘要

本文研究两类以最小化最大完工时间为目标、批容量有界的并行分批排序问题——工件加工时间非增的并行分批在线排序问题和并行分批排序博弈问题。
　　工件加工时间非增的并行分批在线排序问题:该类排序问题模型中有刀个工件要在1台批处理机上加工，每个工件Jj（1≤j≤n）有一个到达时间rj和一个加工时间Pj，工件的加工时间是非增的即对于任意两个工件Ji和Ji，如果ri≤rj则pi≥pj;加工机器为批处理机，每台机器至多可同时加工b个工件，同一批中的工件同时开工、同时完工。该排序问题的研究任务是设计一个在线算法对工件进行合理地分批和排序以使得最大完工时间尽可能达到最小。本文第二章证明了该类排序问题不存在竞争比小于1+α（其中α2+α=1）的在线算法，其次设计了一个竞争比等于1+α的在线算法，进而证明该在线算法是最优的。
　　并行分批排序博弈问题:在该类排序模型中有n个工件待加工，它们具有独立性和自利性，m台批处理机，每台机器至多可同时加工b个工件，每一批的批加工时间为该批中最长工件的加工时间，并且同一批中的工件具有相同的开工时间和完工时间;每个工件Jj（1≤j≤n）都对应一个局中人，局中人的策略集是机器的集合，目标函数是最小化自身的完工时间，而全局目标函数是最小化最大的完工时间。该排序问题研究任务是设计合理的协调机制来影响、引导工件进行选择以使得最大完工时间尽量达到最小。本文第三章为该类排序问题设计了协调机制，并通过相应的算法证明了在该机制下纳什均衡的存在性，同时证明了该机制的无秩序代价为2。