發(fā)布時(shí)間：2018-10-08 07:36

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2255949