线形网络上单台车辆分群调度问题

发布时间：2018-10-08 07:36

【摘要】：本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n~2)时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。
[Abstract]:In this paper, we study the single vehicle clustering scheduling problem on linear networks: a number of customers are distributed on a straight line and they are divided into several continuous subsets, each of which is called a group; Each customer has a release time and a service time; a machine serves all customers and requires continuous customer service within each cluster; the goal is to minimize the long schedule. The problem has two forms: return and non-return. The return timesheet is defined as the time when the machine returns its initial location after all customers are served, while the non-returnable timesheet is defined as the maximum completion time for all customers. Our results are as follows: for every customer with zero service time, it is proved that the two forms can be solved in O (n ~ (2) time, and for any case where each customer's service time is arbitrary, 16 / 9 and 13 / 7 approximate algorithms are given, respectively.
【作者单位】： 上海海洋大学信息学院;华东理工大学理学院;
【基金】：国家自然科学基金项目(11171106,11301184) 上海海洋大学博士科研启动基金(A2-0302-14-300079)
【分类号】：O224

【相似文献】

相关期刊论文 前10条

1 刘振宏;组合最优化问题的近似算法[J];数学的实践与认识;1983年03期

2 马绍汉;一类限制树问题的复杂性及其近似算法[J];山东大学学报(自然科学版);1984年01期

3 杨延龄,戚文发;关于最优备件问题的近似算法的研究[J];工程数学学报;1989年01期

4 杜林古;;带风向投递员问题的一个多项式1—近似算法[J];山东纺织工学院学报;1992年01期

5 何勇;带核集分划问题的一个线性(1/7)-近似算法[J];高校应用数学学报A辑(中文版);1997年04期

6 季敏,何勇;带核集分划问题的一个改进近似算法[J];系统工程理论与实践;2003年12期

7 何晓琼;陈冲;李荣珩;;工厂地址集中的k-种产品选址问题的近似算法[J];计算机工程与应用;2010年08期

8 李亮,叶尚辉;工程结构可靠性分析中高维概率积分的一种近似算法[J];应用力学学报;1989年02期

9 程建纲,秦成林;多处理机调度问题的一种近似算法[J];烟台大学学报(自然科学与工程版);1997年03期

10 黎煜;徐大川;;带次模惩罚的仓库—零售商网络设计问题的近似算法[J];应用数学学报;2012年02期

相关会议论文 前2条

1 梁国宏;郭云霞;郑明发;;最大化下模函数的近似算法及其性能保证[A];第十届中国不确定系统年会、第十四届中国青年信息与管理学者大会论文集[C];2012年

2 任建峰;张玉忠;孙国;;一种新的柔性车间排序问题[A];中国企业运筹学学术交流大会论文集[C];2005年

相关博士学位论文 前1条

1 陈仕平;若干组合优化问题的近似算法设计与分析[D];浙江大学;2002年

相关硕士学位论文 前9条

1 王敏;基于图特征的介度中心近似算法研究[D];曲阜师范大学;2015年

2 张亚平;最小赋权连通k-子图覆盖问题的近似算法[D];新疆大学;2015年

3 张永俊;广义非线性分式规划问题的近似算法[D];河南师范大学;2015年

4 朱婷婷;具有不同释放时间的单机重新排序问题的近似算法[D];兰州大学;2016年

5 王克红;均匀限制NP-完备间题及其近似算法设计[D];云南大学;2016年

6 申子慧;广义多乘积规划问题的近似算法[D];河南师范大学;2016年

7 李彦杰;连通控制吸收集的近似算法[D];新疆大学;2013年

8 刘海;非光滑问题的三次近似算法[D];北京工业大学;2014年

9 张诸俊;异构车辆路径问题近似算法的研究[D];华东师范大学;2014年

，

本文编号：2255949