运筹学排序中的排序算法

Question

运筹学排序中的时间在线排序，其中的在线LPT算法，是在任何时刻当有机器出现空闲，就从当前已经就绪的还没有加工工件中选择加工时间最大的工件安排在这台机器上加工，工件按时间在线到达，即一个工件只有被释放之后才能知道它的一切信息，请标出每一步步骤的含义，并举例说明

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

对于在线LPT算法，可以按照以下步骤进行实现：

1. 创建一个空的待加工工件集合ready，其中工件按照自身需要的时间从大到小排序。
2. 初始化一组空闲机器集合idle，每当有机器处于空闲状态时将其加入idle中。
3. 当一个工件到达时，将其加入ready中，并按照需要的时间从大到小排序。
4. 当一个机器变为空闲时，从ready中选择加工时间最长的工件，将其分配给这台机器加工，直到所有工件都被分配完毕。

举个例子，假设有三台机器和五个工件，其所需时间为：

工件1：4 工件2：2 工件3：6 工件4：3 工件5：5

按照在线LPT算法进行排序的过程如下：

1. ready集合为空，idle集合包含三台机器。
2. 工件1到达，加入ready集合，ready集合为{工件1}，idle集合为{1, 2, 3}。
3. 工件2到达，加入ready集合，按照所需时间排序，ready集合为{工件1, 工件2}。
4. 空闲机器1选中工件1进行加工，此时ready集合为{工件2}，idle集合为{2, 3}。
5. 工件3到达，加入ready集合，按照所需时间排序，ready集合为{工件3, 工件2}。
6. 空闲机器2选中工件3进行加工，此时ready集合为{工件2}，idle集合为{2, 1}。
7. 工件4到达，加入ready集合，按照所需时间排序，ready集合为{工件2, 工件4}。
8. 空闲机器1选中工件2进行加工，此时ready集合为{工件4}，idle集合为{1, 2}。
9. 工件5到达，加入ready集合，按照所需时间排序，ready集合为{工件3, 工件4, 工件5}。
10. 空闲机器3选中工件5进行加工，此时ready集合为{工件3, 工件4}，idle集合为{1, 2, 3}。
11. 机器1完成工件2的加工，从ready集合中选取加工时间最大的工件4进行加工，此时ready集合为{工件4}。
12. 机器2完成工件3的加工，从ready集合中选取加工时间最大的工件4进行加工，此时ready集合为空。

最终的加工顺序为工件1、工件3、工件2、工件5、工件4。