工件带安装时间的单机排序问题的列生成算法

Time-Indexed Formulations for 1|t_(i,j),r_i|∑w_iC_i:Column Generation

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.

We consider the problem of sheduling jobs on single machine with the adjusted time among the processing so as to minmuize the total weighted completion time of jobs. Firstly, a time-indexed formulation is showed and we provide a column generation algorithm for the problem. Then we propose an approximation scheme based the time-indexed formulation. Our algorithms are capable of optmally solving medium sized problem within a resonable computational time.