东华理工大学学报(自然科学版)
東華理工大學學報(自然科學版)
동화리공대학학보(자연과학판)
JOURNAL OF EAST CHINA INSTITUTE OF TECHNOLOGY(NATURAL SCIENCE)
2012年
4期
443-448
,共6页
调度%位置依赖%上界约束%总完工时刻%总负荷
調度%位置依賴%上界約束%總完工時刻%總負荷
조도%위치의뢰%상계약속%총완공시각%총부하
为了研究更具实际意义位置依赖的单机调度和平行机调度决策问题,建立了带有上界限制的一般性位置依赖工件加工时间模型.在模型中,工件实际加工时间表示为初始加工时间和调度位置的一般函数.此类函数没有特殊函数形式和函数单调性的限制,且其函数值不能超过给定上界.对于单机调度问题和平行机调度问题,研究目标函数分别为最小化总完工时刻和最小化机器总负荷.通过分析证明和把所研究的问题模型转化为经典任务分派问题,进而分析得到求解各个问题的计算复杂度.研究表明,在带有上界限制的一般性位置依赖的工件加工时间模型假设下,所研究调度问题都是多项式时间可解的.
為瞭研究更具實際意義位置依賴的單機調度和平行機調度決策問題,建立瞭帶有上界限製的一般性位置依賴工件加工時間模型.在模型中,工件實際加工時間錶示為初始加工時間和調度位置的一般函數.此類函數沒有特殊函數形式和函數單調性的限製,且其函數值不能超過給定上界.對于單機調度問題和平行機調度問題,研究目標函數分彆為最小化總完工時刻和最小化機器總負荷.通過分析證明和把所研究的問題模型轉化為經典任務分派問題,進而分析得到求解各箇問題的計算複雜度.研究錶明,在帶有上界限製的一般性位置依賴的工件加工時間模型假設下,所研究調度問題都是多項式時間可解的.
위료연구경구실제의의위치의뢰적단궤조도화평행궤조도결책문제,건립료대유상계한제적일반성위치의뢰공건가공시간모형.재모형중,공건실제가공시간표시위초시가공시간화조도위치적일반함수.차류함수몰유특수함수형식화함수단조성적한제,차기함수치불능초과급정상계.대우단궤조도문제화평행궤조도문제,연구목표함수분별위최소화총완공시각화최소화궤기총부하.통과분석증명화파소연구적문제모형전화위경전임무분파문제,진이분석득도구해각개문제적계산복잡도.연구표명,재대유상계한제적일반성위치의뢰적공건가공시간모형가설하,소연구조도문제도시다항식시간가해적.