两台单机的合作排序问题

Cooperative Scheduling Between Two Single Machines

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.

The problem with which we shall be concerned relates to the following situation： Two agents jointly process a set of jobs received from customers. Each agent has a single machine and each job will be processed by one of the two machines without interruption. Both agents will get their profits and pay processing costs after finishing the jobs assigned to them. We will find an optimal bipartition of all jobs such that the multiplication of the two agents＇ net profits is maximized. We discuss three models with different classical scheduling objectives as the processing costs. For each model, we show the complexity, analyze the optimality and develop dynamic programming algorithm.