多机调度问题 scheduling problem of multicomputer
该问题作为一个NP hard 问题，属实引起了我的一点兴趣。
不过个人并不是数学强手，只能首先整理和收集大量的NP hard问题，以及寻求目前来说能够值得做的解法。
问题描述
设有n个独立的作业{1, 2, …, n}，由m台相同的机器{M1, M2, …, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。
解法思路
目的是为了将三台机器的处理时间平均分配，理想情况则需要让每台机器的处理时间都大致接近单台机器处理所有任务的总时间的1/3，然而由于任务的随机性，并不能完美保证任务的分配能使每台机器都接近1/3。
那么则需要通过权重值判定每个任务应该交由哪一台处理器处理。
重点来了：一旦我们每台机器都有任务需要处理时，那么我们就应该优先将新的任务交给最先完成任务的处理机。
那么任务有序的情况下，优先分配的工作一定是工时长的，后续分配的工作工时更短，则在处理机有任务时，分配更短的任务更容易保证：原本最先处理完任务的处理机被分配任务后不会突然遇到这样一个情况 “接到一个非常漫长的任务，而如果将先前的任务分配给其他处理机反而会更好”
而通过将任务按照工时降序排列，并将处理机用优先队列存放，则是实现的最优方式。
解法步骤
- 通过降序排序先将任务排序好。
- 通过优先队列将多机分别存储，并以被占用时间升序为优先队列权重排序方式，被占用最少的优先出队，相同则先入队者出队。
- 依次从优先队列取出处理机，依次从有序任务列表中取出尚未处理的任务，并根据出队出列表的顺序依次将任务布置给处理机。
实现代码
待实现