带期限的作业排序问题（分支限界法解决）

一、问题描述

1、Pi指的是如果没有在期限值之前完成，会有Pi的罚款
2、ti指的是完成这个作业所需的时间
3、di指的是这个作业的deadline
目标解释：也就是在最终的解集合里面的作业是都可以按时完成的，而不在最终解集合里面的作业就是不能在对应的期限内完成的作业，这些作业就要计算他们的罚款，其实也就是选择当下这个解集合所需要的成本。

二、元组大小可变的状态空间树

• 节点1表示所有作业都未放入解集合
• 节点2表示的是第一步将作业1放入解集合里；节点3表示作业1被舍弃，第一步就把作业2放进了集合；节点4表示的是把作业1，作业2舍弃，作业3被放入解集合里；节点5表示作业1，作业2，作业3均被舍弃，将作业4 放入解集合中。（注意：排在当前作业之前的作业是被舍弃的，后来不需要再考虑这部分作业）
• 节点8为什么是不可行节点？
  
  上图是所举例子的相关数据，作业1和作业4的截止期限和执行时间都为1，但是不是因为相等哦，就是在这个时候1已经要完成了，同等时间作业4就不能完成了，所以是节点8是不可行节点，不是一个可行解。

C(x)的定义

举个例子：

节点6 指的是作业1和作业2放入，作业3和作业4未放入，所以节点的罚款数（成本）是6+3=9
节点7是作业1，作业3放入，作业2、作业4未放入，所以节点的罚款数（成本）是10+3=13
而C(x)的定义是以该节点为根的子树中最小罚款（⚠️当前所在的节点的罚款也要计算）
节点2的原罚款数是10+6+3=19，但是其实不用算因为这个如果有子树的话一定从当前未选的里面选择了新的，所以肯定比这个节点的原罚款数要小。

== 如何设置成本的估计函数？？？==

估计函数应该是成本的下界（也就是我必须要消耗的成本，躲也躲不掉的成本）

意思就是在当前节点肯定被舍弃掉的作业的惩罚值的和就是在当前节点的成本下界。

节点1没有被舍弃的就是下一步都被选上了所以C(1)=0，节点2没有被舍弃的值所以C(2)=0；节点3舍弃了作业1，所以成本下界为作业1的罚款（成本）C(3)=5；不可行的节点是∞。

形式化描述

• m是在当前作业之前没有写进去的作业的和
• 多了一个节点成本上界，就在节点x的位置所有未在当前节点的解集合中的元素的惩罚值之和
• 对于这个公式的理解，就是随着当前解集合的逐步扩大，成本上界是不断缩小的，如果下一个解集合对应的成本上界比上一层的小就进行更新。（最后的节点的成本上界应该和成本下界相等????）
• 

三、使用FIFO分支限界具体实现

解释：

• 每一步计算每个节点对应的C(x)和U(x)的值，计算过程如上图左上角。
• 上图绿色部分框框里面得到的上界值在减小说明当前整个问题的解的上界在缩小，更加趋近最优解，而计算C(4)=15，它的最小下界比之前的可能的解集合的最大上界都大，所以这个节点就被舍弃了B。
• 在节点在放入 时候，首先考虑当前节点的deadline，不满足直接设置成方形节点，如果满足再考虑当前节点的C????值和U的值是否符合相应的条件，先看当前节点的C????值是否比U值小，如果不满足这个节点被kill，再看如果新计算出的U比当前的U小就更新U，如果大的话不变!
  
• 是否满足每个节点的C????值都是C值的下界？？对于答案节点来说，C????值不等于C值

总结

• 带期限的作业问题的目标：当前解集合下，所有未在解集合中的作业的成本（罚款——之和最小
• 元组可变的状态空间树的形成
• C(x)和C????(x)的定义：C(x)——以X为根的子树中节点的最小罚款；C????(x)——所有确定不在解集合中的元素的罚款之和（一个是从下往上，一个是从上往下，只对已知的进行操作）
• 使用FIFO的具体实现，使用LIFO实现，使用LC分支限界法实现