江西科学
江西科學
강서과학
Jiangxi Science
2015年
5期
647-651,707
,共6页
混合型平行机调度%可中断工件%注水模型%最小化时间表长%多项式时间算法
混閤型平行機調度%可中斷工件%註水模型%最小化時間錶長%多項式時間算法
혼합형평행궤조도%가중단공건%주수모형%최소화시간표장%다항식시간산법
hybrid parallel machine scheduling%preemptive job%affusion model%makespan minimiza-tion%polynomial time algorithm
考虑部分机器需要周期维护,其余机器无需维护的混合型平行机调度问题. 一组给定的可中断且加工时长均相等的工件需要加工,工件数不超过机器数. 目标是将所有工件安排到机器上加工,使得时间表长最小. 首先分析一些特殊情况;然后对于一般情况通过建立注水模型给出最优时间表长的一个下界;接着对水位的2种情况分别给出目标值等于下界的多项式时间算法;最后给出了求解该调度问题的一个多项式时间最优算法.
攷慮部分機器需要週期維護,其餘機器無需維護的混閤型平行機調度問題. 一組給定的可中斷且加工時長均相等的工件需要加工,工件數不超過機器數. 目標是將所有工件安排到機器上加工,使得時間錶長最小. 首先分析一些特殊情況;然後對于一般情況通過建立註水模型給齣最優時間錶長的一箇下界;接著對水位的2種情況分彆給齣目標值等于下界的多項式時間算法;最後給齣瞭求解該調度問題的一箇多項式時間最優算法.
고필부분궤기수요주기유호,기여궤기무수유호적혼합형평행궤조도문제. 일조급정적가중단차가공시장균상등적공건수요가공,공건수불초과궤기수. 목표시장소유공건안배도궤기상가공,사득시간표장최소. 수선분석일사특수정황;연후대우일반정황통과건립주수모형급출최우시간표장적일개하계;접착대수위적2충정황분별급출목표치등우하계적다항식시간산법;최후급출료구해해조도문제적일개다항식시간최우산법.
Consider a hybrid parallel machine scheduling problem where some machines need period-ic maintenance while the rest of the machines do not need any maintenance. A set of preemptive jobs with equal processing time need to be processed and the number of jobs is not greater than that of the machines. The objective is to schedule all the jobs to the machine such that the makespan is mini-mized. This paper first analyses some simple cases,and then proposes a lower bound for the optimal makespan of the complex case based on the establishment of a affusion model;thereafter,proposes a polynomial time algorithm for each of the two cases of the water level;finally,presents a polynomial time optimal algorithm for the scheduling problem under consideration.
