冯 琪, 杨丽华, 狄 帅

(1- 中原工学院理学院，郑州 450007; 2- 京东数字科技，北京 100015)

1 引言

排序(调度)就是在一定的条件下对工件(产品)和机器按时间进行分配和安排加工次序，使一个或多个指标达到最优.机器制造业的发展是排序发展的主要推动力.后来，随着社会的进步和经济的快速发展，在人们的工作和生活中产生了越来越多的排序问题.例如：如何将原材料放在机器上加工成人们需要的各种产品，并且用料最省或利润最大？如何将生产出来的零件以一定的次序快速组装成产品？在大型工程的兴建中，如何对各类人员进行安排，对各种器材的供应进行调度？对于种类繁多的网购物品，快递公司如何调度，使得快递员以最快速度把大量物品送到客户手中？这些都是排序问题.因此，在现代化的生活中，服务业、制造业、运输业、计算机科学等领域都有它的大量应用.排序的好坏直接影响着费用的高低和利润的大小！大多数经典排序文献所考虑的工件仅属于一个代理(客户).而在实际问题中，被加工的工件往往属于不同的代理.例如，一个企业或生产厂家，需要同时面对不同的客户，并且这些客户要竞争着使用共同的资源，假如两个客户的订单需要在同一时间、同一台机器或者同一个流水线上加工，决策者如何调度才能使利润最大化，并且让不同的客户都达到满意.因此，为了满足不同代理的需要，决策者需要在多个代理的利益之间……