带安装时间的单机排序问题的讨论

《带安装时间的单机排序问题的讨论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Abstract—Stu—dyonSomesingle枷ach堕scI!!堕!啦墅坐堕!些Setup’n“塑StudyonSomeSingle-MachineSchedulingProblemswithSetupTimesSchedulingproblemisoneoftheimportantcombinatorialoptimizationproblems．Thisthesisdiscussesthesinglemachineschedulingproblemwithinstallationtime，group

2、technology(GT)，resourceconstraintsandavariableprocessingtime．Thisthesisconsistsofsevenchapters．Chapter1introducessomebackgroundinformationoftheschedulingproblem．Chapter2discussessomeschedulingproblemswithsetuptimesinwhichobjectivefunctionsarethemaximumcomplet

3、iontime，totalcompletiontimeandthetotalabsolutedeviationofcompletiontimerespectively．Inthispaperpolynomialalgorithmsalegivenforoptimallysolvingproblems1Ichains，s州lc吣，1lSpsdbI，⋯，饥)ITCand1ls删慨，⋯阮)lTADC．Inchapter3thesinglemachineschedulingproblemwithgrouptechnolo

4、gyandpsdinstallationtimeslI$psd，GTI∑C』isdiscussed，andapolynomialtimealgorithmisdescribed．Chapter4concernstheenvironmentwithsetuptimeandlearningeffect，andtheobjectiveistominimizethetotallateness，totaltardinessandthemaximumlatenessrespectively．Undercertaincondi

5、tions，polynomialtimealgorithmsforoptimallysolvingproblemslLE，psdl∑0，11LE，mdl∑乃andlILE，t,salkalepresented．Chapter5takesintoaccountresourceconstraintsandadeterioratingeffectinasinglemachineschedulingwithGT．AnoptimalsolutionprocedureforproblemlI墨=厂Qi)'G，P{，(口+所l

6、∑蚝suIG嗽isgiven．Inchapter6schedulingproblem1Jchains，s州Ic眦withchainconstraintsandpsdinstallationtimesisdiscussedandapolynomialtimealgorithmforoptimalsolutionisproposed．Chapter7givessummaryofthethesis，andfurtherresearchworkinfutureissuggested．Keywords：single--ma

7、chinescheduling；learningeffect；deterioration；grouptechnology；set-uptimes；resourceconstraints；polynomialtimealgorithmWHitenbyXiaoJunSupervisedbyProf．WenZhenweiⅡ目录第一章引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1排序问题概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2论文各部分主要内容介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

8、⋯⋯⋯⋯⋯⋯⋯⋯⋯．．4第二章带有安装时间的排序问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯52．1问题简介及描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．52．2问题1ISpsd(bl，bl，．．．，阮)lc眦的求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．3问题lIS珊d(bl,轨，．．．，阮)ITC的求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．4问题