动态规划解决车间调度问题

Question

问题如下：
有j1,j2,j3,j4,...,j20共20道作业，在两台并行的同功能的机器m1,m2上加工。每道作业有个最迟完成时间。如果超出了这个时间，就有个滞后时间。现在的要求是，如果将这20道作业分配到这两台机器上，使得两台机器最迟完成时间最小。比如一共需要50个小时，m1上分配30个小时，m2上分配20个小时，那么两台机器的最迟完成时间为30小时；如果m1上分配24,m2上分配26,那么两台机器的最迟完成时间为26。同时要求滞后时间之和最小。请各位大侠仔细看下问题。如果仅仅求滞后时间和最小，用贪心算法就行了（对最迟要求完成时间排序），但这问题还多了个条件，就是要使两条机器的完成时间差距越小越好（因为两台机器的总共完成时间之和是常量）。因此，如何将这个问题用动态规划来求，一直没想好。这是我们老大要求的，请各位帮帮忙不甚感激

Answer 1

从20道作业随即取10道，相加作业最迟时间只和减总时间之和的一半，在这10道作业中选取一个作业与这10道作业意外的一个作业相减等于这余下的值的话就将这两个作业位置调换。举个6个作业的列子，加入他们最迟完成时间为x1=10,x2=9,x3=8,x4=10,x5=3,x6=4,他们总作业时间为44小时，的一半就为22小时，现在随即选取3个作业给机器x=x1+x2+x6=10+9+4=23 23-22=1 剩下的3个作业为x3=8,x4=10,x5=3 已经分配的作业中只有x5-x4=4-3=1 所以x6与x5调换 基本就是这个原理 如果20道作业的话 调换的可能性也就多点 不光是一个调换