第34卷第7期 2017年7月
吉林化工学院学报
JOURNAL OF JILIN INSTTTUTE OF CHEMICAL TECHNOLOGY
文章编号：1007-2853(2017)07-0077-03
到达顾客时间总和最短的排序及运输
李岩，谢百成？
Vol.34 No.7 Jul.2017
（1.吉林化工学院理学院，吉林吉林132022;2.中国电力工程顾问集团东北电力设计院有限公司，吉林长春130021 摘要：生产和运输中的一个重要的问题是把生产和运输相结合.建立一台机器进行加工工件，并且把工件运送给不同目的地的多个顾客，目标函数是使到达顾客的时间最短.此问题在一般情况下是NP-难的
当顾客的数量是固定时，设计了动态规划算法，并对几种特殊情况设计了更有效的算法关键词：排序；动态规划；物流调度；运输
中图分类号：0226
文献标志码：A
排序与供应链在不同阶段的合作受到了很多关注，这个领域研究的的一个很重要的问题是从工广到顾客的运输阶段.传统的排序模型只考虑了生产排序的阶段而没有考虑生产和运输的结合.这些模型中假设车辆的利用是无限的，因此加工完成后的工件可以随时运送到顾客而没有延误.但是在实际中车辆的数量是有限的，有时不能够及时的运送完工的工件而导致工件到达顾客的时间延后.本文中，我们加人了一台车辆的运输情况，目标函数是确定工件在工厂的加工顺序并运输到顾客使总的时间最小
一些排序模型研究过相关的问题.早期的研究是Maggu和Das1].他们考虑了两台机器的柔性流水作业，车辆有无限大的容量使得工件加工完成后可以立即运送给顾客.Kiseetal.[2]考虑了车辆一次只运输一个货物的情况.Langston[3]， Panwalkar4]，Sahni和 vairaktarakis5]，Stern和 Vitner[6], Stevens 和 Germill[7], Vairaktarakis[S] 研
究了类似的问题[9-13]。 1最优性
下面对本文要研究的问题进行介绍.n个工
件J,J，J。在一台生产设备上进行加工，每个工件都有固定的加工时间和相关联的顾客.共有m个顾客并且这m个顾客所处的位置不同.存在一个运输工具其容量是K（K≤n）使得一次最
收稿日期：2017-04-17
基金项目：国家自然科学基金项目（2012029）
DOl:10.16039/j.cnki.cn221249.2017.07.018
多可运输k个工件.如果运输工具不受容量的限制，则假设k<8.当工件加工完成后，需要利用运输工具将其送到顾客处.在0时刻所有工件都可以被加工并且运输工具也是可以使用的.我们需要确定工件的加工顺序，工件离开工厂的时间以及运输路线来使工件到达顾客的时间最短.为了简单起见，假定工件J,J2，."，J.按照SPT（非减
顺序）规则排序[14-16] 1.1符号说明
n：工件的数量（JJ2，".,J.）按照SPT规则排序
P：工件J：的加工时间
P.J,J2，.，J的加工时间之和 m：顾客的数量
n：运送到顾客k的工件的数量 P""：J*的加工时间
P）="P"工件J",J，",J")的加工时间
K：运输工具的容量,K≤n
to：从工厂到顾客k的运输时间 tu：顾客k到1的运输时间
C：工件J，在工厂的完工时间 C工件J；到达顾客的时间 1.2最优性
目标函数是使所有工件到达顾客的时间最
短.即得到下面的规划：
作者简方数据（1982-），女，吉林四平人，吉林化工学院讲师，硕士，主要从事运筹学与控制论方面的研究