摘要
供应链排序研究了两个部分的问题,第一部分是权重不一致的工件在一台机器上加工,第二部分是把加工完的工件分成若干批按照某种运输方式运输,并且运送到预先指定的目的地,目标是求加权完工时间与运费总和最小.我们将用已知的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.
出处
《吉林化工学院学报》
CAS
2016年第5期85-87,共3页
Journal of Jilin Institute of Chemical Technology
关键词
分批排序
供应链
三划分
NP-难
近似算法
batching
supply chain
three-partition
NP-hard
approximation algorithm