考虑常数客户批运输的单机排序问题

《考虑常数客户批运输的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第５期运筹与管理Ｖｏｌ．２２，Ｎｏ．５２０１３年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１３考虑常数客户批运输的单机排序问题汪磊扬（华东理工大学理学院数学系，上海２００２３７）摘要：本文考虑工件首先在单机上加工，完工的工件由一辆容量有限的车配送到指定客户的模型，目标是最小化ｍａｋｅｓｐａｎ。对于工件物理大小相同的情况，我们考虑了常数个客户的情形，并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况，我们讨论了一类特殊的三个客户的情形，并给出了一个２-近似算法。关键词：组合最优化；排序；近似算法；批运输

2、；常数客户中图分类号：Ｏ２２３文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０５-００２９-０６SingleMachineSchedulingwithBatchDeliverytoMultipleCustomersＷＡＮＧＬｅｉ-ｙａｎｇ（Dept．ofMathematics，EastChinaUniversityofScienceandTechnology，Shanghai２００２３７，China）Abstract：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｃｏｎｓｉｄｅｒｔｈｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｉｎｗｈｉｃｈｔｈｅｊｏｂｓａｒｅｆｉｒｓｔｐｒｏｃｅｓｓｅｄｂｙｏ

3、ｎｅｓｉｎｇｌｅｍａｃｈｉｎｅａｎｄｔｈｅｎｄｅｌｉｖｅｒｅｄｉｎｂａｔｃｈｅｓｂｙａｓｉｎｇｌｅｖｅｈｉｃｌｅｗｉｔｈｌｉｍｉｔｅｄｃａｐａｃｉｔｙｔｏｔｈｅｒｅｓｐｅｃｔｉｖｅｃｕｓｔｏｍｅｒｓ．Ｔｈｅｇｏａｌｉｓｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｋｅｓｐａｎ．Ｆｏｒｔｈｅｉｄｅｎｔｉｃａｌｊｏｂｓｉｚｅｃａｓｅ，ｗｅｐｒｅｓｅｎｔａｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍｗｈｅｎｔｈｅｎｕｍｂｅｒｏｆｃｕｓｔｏｍｅｒｓｉｓｆｉｘｅｄ．Ｆｏｒｔｈｅｎｏｎ-ｉｄｅｎｔｉｃａｌｊｏｂｓｉｚｅｓｃａｓｅ，ｗｅｃｏｎｓｉｄｅｒａｓｐｅｃｉａｌｃａｓｅｗｉｔｈｔｈｒｅｅｃｕｓ-ｔ

4、ｏｍｅｒｓａｎｄｄｅｖｅｌｏｐａ２-ａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍ．Keywords：ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎ；ｓｃｈｅｄｕｌｉｎｇ；ａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍ；ｂａｔｃｈｄｅｌｉｖｅｒｙ；ｍｕｌｔｉｐｌｅｃｕｓｔｏｍｅｒｓ０引言在最近几年中，多阶段协作的供应链排序问题得到很大的关注。传统的排序问题只考虑工件的加工，而在现实世界中，大部分的制造企业需要把完工的产品配送到不同客户或仓库。本文考虑了加工和配送相互协作的两阶段排序问题，该问题可以描述如下：有n个工件的集合N＝｛J１，J２，⋯，Jn｝首先在位于中心的单机上加工

5、，然后由一辆容量有限的小车运输到指定的客户。这里我们考虑总共有m（m≤n）个客户分布在不同的位置。每一个工件Jj有一个加工时间pj和物理大小sj，这里的sj表示工件Jj在车上占用的物理空间。车辆的容量，即一次运输提供的最大空间为z。一起运输的工件称为一个配送批。初始时刻车辆和工件都在中心可用。目标是确定工件在单机上的加工顺序及配送规则，使得车辆运输完所有工件且回到中心的时间最小。［１］［２］如果所有客户都分布在同一个位置，且工件的物理大小都相同，Ａｈｍａｄ等及Ｌｅｅ等都给出了最优算法。但是客户分布在一般网络的顶点上或者工件具有不同的物理大小的问题都是强ＮＰ困难的。因为前者包含

6、了ＴＳＰ问题为它的特殊情况，而后者包含了装箱问题为它的特殊情况。［３］对于工件物理大小相同的情况，Ｌｉ等考虑了客户分布在一般网络的问题，但是他们的目标是极小化完工时间和。对于客户数量为常数的情况，他们给出了一个多项式时间的动态规划算法。Ｌｅｖｉｎ和［４］Ｐｅｎｎ考虑了一个类似的问题，他们假设有任意多个客户及一辆容量无限的小车，并且给出了一个收稿日期：２０１２-０７-２７基金项目：国家自然科学基金资助资助项目（１０７７１０６７）作者简介：汪磊扬（１９８３-），男；博士研究生，主要研究方向：组合最优化，排序理论。３０运筹与管理２０１３年第２２卷６e≈１６．３０９６９１-近似的算法

7、。［５］对于工件的物理大小不相同的情况，如果所有客户都分布在同一个位置，Ｃｈａｎｇ等最早给出了２-近［６］似算法。接着，Ｚｈｏｎｇ等改进了算法，进一步给出了３／２＋ε-近似的算法，但是他们的算法需要调用背包［５］问题的完全多项式近似方案。如果客户分布在两个不同的位置，Ｃｈａｎｇ等给出了一个２-近似算法。本文考虑客户数量为给定常数的情况。接下来的内容安排如下。在第１节中，考虑工件物理大小相同的情况，给出了一个动态规划算法。在第２节中，考虑工件物理大小不同的情况，对于一类特殊的三个客户的情形，给出了一个２-