单处理机在加工时间相同准备时间可控时的ΣwjCj问题.pdfVIP

维普资讯 排序多＆杯，单 理杌，加工日习 第7卷 第 1j9l 应用数学 与计算 数学学 报 VoL7 No．1 1993年 6月 COMM ．ONAPPL． ￡ATH．AND COMPUT Jun．．1993 单处 理 机在 加’工 时 间相 同 一 准 备 时 间可 控 时 的~,,wfCi问题 ● 孙 世 杰 02z] (上毒科拄大学) TheSchedulingProbbm oftheTotalW eighted CompletionTimeonA SingleMachineaStheProcessing TimesIdentiCalandtheReadyTimesContr01]able ． SunShljie ， fs 唧 UnieerKty耐Scienceand chnd } Abstraet Agroupofnjobsneedtobeprocessedonasinglemachine．Forjob theready tim eandhteprocessingtimeneededaxeriand respectivelylandtheready tERle , canbereducedis ，10Sz 0】allhtenumberri，P1，，arenonnegatlveintegers． Byt：hefirstobjectlve“nctlon relatedtozandSchedulingandthecdmpressing cost weconstructfourumhlpleobjectiveschedulingproblems：(P1)-(P4)iIlour p~tpor,Themultipleobjectiveschedulingproblemswhichrelatedtothecontrollable ready timeswasfilstconsideredby Nowickiand Zdrzalka，in theirpapertheytook n asmakespalt，provedtheproblem (Pl】·(P3)WerestrollgNP—CIndgaveall approximativealgoritlimforproblems(P1)．。Wetakethetotalweightedcompletion thneSasFlinourpapernadgivetheoptimalMgorihtmfortheproblems(P1)-(P4) oiltheconditionthatalltheprocessingtimePiareequaltoone． 一 组n个工件需在_|台机 {}{}上加工，工件 所需的准嵛 t间、加工时间分别为 rJ， ，可压缩准嵛ut间为q，0 q rJ， 中0 PJ，q 均为非负整数．山同压缩向 量 有关的某一丹标 函数 和压缩 费用B =E 可构成文 中的四个多 目标排序 问题 (P1)：(P4)这种_口』控准嵛时间的多 日标排序 问题山引文 2【】的作者在1990年提出并作 了研究．文12】研究的是在应交工时间存在吖的相应多 目标排序 问题 (P1)-(P3)，其 中 取l，l=a ( )，为序，证明了(P1}，因而(P21、(P3J为NP