多机调度问题： 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。 请给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。写出算法思想、伪码，并证明其正确性

算法思想：

该问题属于经典的多机调度问题，可以采用贪心算法解决。具体算法流程如下：

1. 将n个作业按照处理时间从大到小排序，得到一个作业序列。
2. 初始化m个机器的完成时间为0。
3. 遍历作业序列，将每个作业分配给完成时间最早的机器。
4. 更新该机器的完成时间，即加上该作业的处理时间。
5. 重复3-4步骤，直到所有作业被分配完毕。

伪码：

Sort jobs in decreasing order of processing time
Initialize the completion time of m machines to 0
For each job in the sorted job list:
    Assign the job to the machine with the earliest completion time
    Update the completion time of the machine
Return the maximum completion time among all the machines

算法正确性证明：

假设存在一种更优的调度方案，使得完成时间更短。我们将该方案与贪心算法得到的方案进行比较。

首先考虑贪心算法得到的方案。按照算法流程，每次都将作业分配给完成时间最早的机器，这样可以保证当前的完成时间是最小的。因此，该方案是满足最小化完成时间的条件的。

然后考虑假设的更优方案。如果该方案中存在某个机器的完成时间比贪心算法得到的方案更早，那么我们可以将该机器上的某个作业移动到其他机器上，不会造成其他机器的完成时间更晚，也不会使该机器上的完成时间更早。这是因为，我们可以将该作业给完成时间最早的机器去处理，这样不仅不会影响其他机器的完成时间，还能使该机器上的完成时间更早。因此，将该作业移动到其他机器上不会影响最优调度方案的完成时间。

综上所述，我们得到结论：贪心算法得到的调度方案是最优的。