三划分转化为供应链排序问题

The transformation of three partition and the supply chain scheduling problems

供应链排序研究了两个部分的问题,第一部分是权重不一致的工件在一台机器上加工,第二部分是把加工完的工件分成若干批按照某种运输方式运输,并且运送到预先指定的目的地,目标是求加权完工时间与运费总和最小.我们将用已知的NP-难题三划分问题转化成本问题来证明此供应链问题是一个NP-难问题,并给出此难题的近似的算法.

We studied the scheduling problem with two phases,in which jobs of different importance are processed on a machine in a certain order processing in the first stage,and in the second stage,the completed jobs need to be batch delivered to various pre-specified destination with a certain kind of transportation modes,the object is designing a recursive algorithm to minimize weighted completion time and transportation cost. We will use the three-partition problem to conversion our problem in this paper,the research problem is a NP-hard problem,and give approximate algorithm of the problem.