一类具有学习效应和安装时间的单机排序问题

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

1、第19卷第3期2010年6月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．19，No．3Jun．2010一类具有学习效应和安装时间的单机排序问题尤金亭，唐恒永(沈阳师范大学数学与系统科学学院，辽宁沈阳110034)摘要：本文主要讨论了工件加工时间具有学习效应和安装时间的单机排序问题。工件的加工时间不仅与之前已加工完的工件加工时间有关，还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数，即p-s．d形式。本文证明了极小化最大完工时同，极小化总完

2、工时间，极小化完工时间的平方和问题具有多项式算法，也证明了极小化加权总完工时间，极小化最大延误和极小化总误工问题在某些条件下具有多项式算法。关键词：运筹学；排序；单机；学习效应；安装时间中图分类号：0223文章标识码：A文章编号：1007-3221(2010)03一0053-07Single·machineSchedulingwithLearningEffectandPast--sequence·dependentSetupTimesYOUJin—ting，TANGHeng-yong(SchoolofMathemat

3、icsandSy,temJScience，ShenyangNormalUniv．，Shenyang10034，China)Abstract：Thispaperstudiesthesingle-machineschedulingproblemwithlearningeffectandsetuptimesconsid—erations．Theactualprocessingtimeofajobdependsnotonlyontheprocessingtimesofthejobsalreadypro—cessedbutal

4、soonitsscheduledposition．Thesetuptimesareproportionaltothelengthofthealreadyprocessedjobs，ie．thesetuptimesarepast·sequence-dependent(p一5一d)．Weshowthatthemakespanminimizationprob—lem，thetotalcompletiontimeminimizationproblemandthesumofthequadraticjobcompletionti

5、mesminimiza·tionproblemcanbesolvedinpolynomialtime，respectively．Wealsoshowthatthetotalweightedcompletiontimeminimizationproblem，themaximumlatenessminimizationproblemandthetotaltardinessminimizationproblemcanbesolvedinpolynomialtimeundercertainconditions．Keyword

6、s：operationalresearch；scheduling；single—machine；learningeffect；setuptimes0引言最近几年，学习效应在排序问题中引起了广泛的关注。Biskup⋯首次提出具有学习效的排序问题。Kuo和Yang【21指出在实际生活中，工件的加工时间可能与已经加工完的工件的加工时间有关，故提出工件的实际加工时间依赖于时间的学习效应模型。Koulamas和Kyparisis"1提出广义的学习效应问题，并将模型推广到了更一般的形式。之后，Cheng，Wu和Lee【41又提出

7、一种新的学习效应模型，即加工时间不仅与之前已加工完的工件加工时间有关，还与工件的加工位置有关。讨论了单机排序的～些问题，其中极小化最大完工时间问题，极小化总完工时间问题是多项式可解的，而极小化加权总完工时间问题，极小化最收稿日期：2009—03-27基金项目：国家自然科学基金资助项目童助(10471096)作者简介：尤全丰(1983．)，女，蒙古族，辽宁姨岭人，项士研究生。主要研究方向为排序理论与算法。54运筹与管理2010年第19卷大延误问题是在某些条件下具有多项式算法的。流水作业问题的极小化最大完工时间问题，极小

8、化总完工时间问题也是在某些条件下是多项式可解的。另一方面，在传统的排序模型中，很有必要考虑带有安装时间的排序问题。Koulamas和Kyparisis"1首次提出带有与顺序相关的安装时间(p．s．d)排序问题，即安装时间是依赖于所有已加工完的工件。Biskup和Herrmann[61在此基础上分析了工件带有p-s—d安装时间和工期相关的一些问题