【摘要】：本文研究線形網(wǎng)絡(luò)上單臺車輛分群調(diào)度問題:若干客戶分布在一條直線上,它們被劃分成若干個連續(xù)子集,其中每個子集稱為一個群;每個客戶有一個釋放時間和一個服務(wù)時間;一臺機器服務(wù)所有客戶,且要求每個群內(nèi)的客戶連續(xù)服務(wù);目標(biāo)為極小化時間表長。該問題分兩種形式:返回型和不返回型。返回型的時間表長定義為機器服務(wù)完所有客戶后返回其初始位置的時間;不返回型的時間表長則定義為所有客戶的最大完工時間。我們的結(jié)果是:對每個客戶服務(wù)時間為零的情形,證明了兩種形式均可在O(n~2)時間內(nèi)解決;對每個客戶服務(wù)時間任意的情形,就返回型和不返回型,分別給出了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.
【作者單位】： 上海海洋大學(xué)信息學(xué)院;華東理工大學(xué)理學(xué)院;
【基金】：國家自然科學(xué)基金項目(11171106,11301184) 上海海洋大學(xué)博士科研啟動基金(A2-0302-14-300079)
【分類號】：O224

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學(xué)的實踐與認(rèn)識;1983年03期

2 馬紹漢;一類限制樹問題的復(fù)雜性及其近似算法[J];山東大學(xué)學(xué)報(自然科學(xué)版);1984年01期

3 楊延齡,戚文發(fā);關(guān)于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學(xué)學(xué)報;1989年01期

4 杜林古;;帶風(fēng)向投遞員問題的一個多項式1—近似算法[J];山東紡織工學(xué)院學(xué)報;1992年01期

5 何勇;帶核集分劃問題的一個線性(1/7)-近似算法[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯(中文版);1997年04期

6 季敏,何勇;帶核集分劃問題的一個改進(jìn)近似算法[J];系統(tǒng)工程理論與實踐;2003年12期

7 何曉瓊;陳沖;李榮珩;;工廠地址集中的k-種產(chǎn)品選址問題的近似算法[J];計算機工程與應(yīng)用;2010年08期

8 李亮,葉尚輝;工程結(jié)構(gòu)可靠性分析中高維概率積分的一種近似算法[J];應(yīng)用力學(xué)學(xué)報;1989年02期

9 程建綱,秦成林;多處理機調(diào)度問題的一種近似算法[J];煙臺大學(xué)學(xué)報(自然科學(xué)與工程版);1997年03期

10 黎煜;徐大川;;帶次模懲罰的倉庫—零售商網(wǎng)絡(luò)設(shè)計問題的近似算法[J];應(yīng)用數(shù)學(xué)學(xué)報;2012年02期

相關(guān)會議論文 前2條

1 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學(xué)者大會論文集[C];2012年

2 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運籌學(xué)學(xué)術(shù)交流大會論文集[C];2005年

相關(guān)博士學(xué)位論文 前1條

1 陳仕平;若干組合優(yōu)化問題的近似算法設(shè)計與分析[D];浙江大學(xué);2002年

相關(guān)碩士學(xué)位論文 前9條

1 王敏;基于圖特征的介度中心近似算法研究[D];曲阜師范大學(xué);2015年

2 張亞平;最小賦權(quán)連通k-子圖覆蓋問題的近似算法[D];新疆大學(xué);2015年

3 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學(xué);2015年

4 朱婷婷;具有不同釋放時間的單機重新排序問題的近似算法[D];蘭州大學(xué);2016年

5 王克紅;均勻限制NP-完備間題及其近似算法設(shè)計[D];云南大學(xué);2016年

6 申子慧;廣義多乘積規(guī)劃問題的近似算法[D];河南師范大學(xué);2016年

7 李彥杰;連通控制吸收集的近似算法[D];新疆大學(xué);2013年

8 劉海;非光滑問題的三次近似算法[D];北京工業(yè)大學(xué);2014年

9 張諸俊;異構(gòu)車輛路徑問題近似算法的研究[D];華東師范大學(xué);2014年

，

本文編號：2255949