带有维修活动和加工时间有关的单机排序
2017-04-13陈耀宁柳秉昉
陈耀宁，柳秉昉
(1.重庆师范大学数学科学学院，重庆401331；2.重庆师范大学教育科学学院，重庆401331)
带有维修活动和加工时间有关的单机排序
陈耀宁1，柳秉昉2
(1.重庆师范大学数学科学学院，重庆401331；2.重庆师范大学教育科学学院，重庆401331)
讨论带有维修活动区间且与时间有关的单机排序问题.工件的实际加工时间是关于这个工件开始加工时间的线性函数，其在加工工件的过程中需要进行维修，维修过程中及不能加工工件，且维修与时间有关.维修过后机器加工工件的速度也发生变化.目标是确定维修的位置及排序，从而使目标函数最小.
单机排序；维修活动；加工时间
一般的排序问题中，工件的加工时间都是可控的，Nowicki等[1]和Shabtay等[2]研究了加工时间可控的排序问题.Panwalkar等[3]研究了单机加工时间的可控性.Cheng等[4]、Yang等[5]和Zhao等[6]研究了工件的加工时间与开始加工时间呈线性相关的单机排序问题.另一方面，单机排序问题中加入了具有维修活动，这样更符合实际问题.Cheng等[4]、Yang等[5]、Zhao等[6]、Yang等[7]和Ang S－J等[8]研究了具有维修活动的单机排序，并提出了相关的算法.在单机排序理论的不断发展中，渐渐加入了工期窗口.Cheng等[4，9]讨论了共同工期窗口的单机排序问题，Yang等[5]、Zhao等[6]和Mosheiov等[10]讨论了时间窗口的单机排序，Yang等[7]在单机排序中加入了松弛工期窗口，Ang S－J等[8]在此基础上研究工期指派问题，Shabtay等[11－12]研究了开放的工期窗口指派问题.
本文考虑的是带有维修活动区间且与时间有关的单机排序问题.目标是确定维修的位置及排序，从而使目标函数最小.
1 问题描述
有n个工件{J1，J2，…，在同台机器上加工，所有工件零时间到达，同一时间机器只能加工一个工件.工件Jj的基本加工时间为Pj.但实际加工过程中工件的加工时间与开始加工时间呈线性函数，表示工件的实际加工时间，且＝Pj＋bSj，Sj为工件Jj的开始加工时间，且＝Pj＋bSj，Sj为工件Jj的开始加工时间.机器在加工完成第i个工件后需要进行一次维修，花费时间为t＝aci，ci表示第i个工件的完工时间，维修过后工件Jj的基本加工时间为SjPj，实际加工时间＝SjPj＋bSj.工件Jj的工期dj＝＋q.Cj，Ej＝max{ 0，dj－cj}.Tj＝max{ 0，cj－dj}.分别表示工件的完工时间、提前时间、误工时间.一般地，工件在完工时会产生一定的费用，包括基本加工费用，提前完工费用，没有完工费用.要确定维修位置以及工件的加工顺序，从而小化总费用目标函数(αEj＋βTj＋γq)＋D.用三参数表示为1 γm，Pj＋bSj∑αEj＋βTj＋γq＋D.
2 问题的分析
工件在不同加工位置上的工期时间和完工时间:
引理1 如果Cj≤dj，则Cj－1≤dj－1，j＝1，2，…，n；如果Cj≤dj，则Cj＋1≤dj＋1，j＝1，2，…，n.
定理1 对于问题1 γm，Pj＋bSj∑(αEj＋βTj＋γq)＋D，最优排序有q＝Ck－1，1≤k≤n，且
证明 设Ck－1≤q≤Ck.不妨设k 由引理1可知，在第k个工件之前工件都是提前的，在第k个工件之后工件都是误工的，用Zj表示第j个工件的提前或误工费用，有: 很显然，A和B都独立于Δ，且B>0.若使Z最小，则有: 所以有q＝Ck－1，且 由以上分析可知，在1≤i 由上述分析不难看出，该问题用指派算法可以求出: Step2:将工件接触PT规则排列并选前k－1个工件排在前k－1个工件上； Step3:将后面的工件按SPT规则排序. 例1 假设n＝6，α＝6，β＝9，γ＝2，a＝b＝0.1，D＝10，各工件的加工时长与开始时间如表1所示. 表1 各工件的加工时长与开始时间Tab.1 Processing time and start time of each job Step2:当k－1个2件顺序为[J1，J2，J3，J4]. Step3:工件的加工顺序为J6→J5→J1→J2→J3→J4，且维修发生在工件J5加工完，Z＝732.88561. 本文讨论了依赖时间的维修活动.需要确定最佳的维修位置，工件的加工顺序从而极小化目标函数.分别从不同的维修位置考虑从而证明这个问题是多项式可解，并且在此基础上提出算法，例子使用Matlab软件编程进行运算的，这样极大的提高了运算速度.进一步的问题可以考虑其他单机问题或者平行机问题，或者考虑多次维修的情形. [1] NOWICKI E，ZDRZALKA S.A survey of result for sequencing problems with controllable processing times[J].Discrete Applied Mathematics，1990，26(2/3):271－287. [2] SHABTAY D，STEINER G.A survey of scheduling with controllable processing time[J].Discrete Applide Mathematics，2007a，155(13):1634－1666. [3] PANWALKAR SS，RAJAGOPALAN R.Single－machine sequencing with controllable processing times[J].European Journal of Operational Research，1992，59(2):298－302. [4] CHENGT C E，YANGS J，YANG D L.ommon due－window assignment and scheduling of linear time－dependent deteriorating jobs and a deteriorating maintenance activity[J].International Journal of Production Economics，2010，135:154－161. [5] YANG S J，YANG D L，YANG Q Y，et al.Single machine due window assignment and scheduling with job－depend aging effects and deteriorating maintenance activities[J].Computers and Operations Research，2010，37:1510－1514. [6] ZHAO C L，TANG H Y.A note to due－window assignment and single machine scheduling with deteriorating jobs and a rate－modifying activity[J]. Computers and Operations Research，2012，39:1300－1303. [7] YANG S－J，HSU C－J，YANG D－L.Single－machine scheduling and slack due－date assignment with aging effect and deteriorating maintenance[J]. Optimization Letters，2012，6(8):1855－1873. [8] AANG S－J，HSU C－J，YANG D－L.Single－machine scheduling with due－date assignment and aging effect under a deteriorating maintenance activity consideration[J].International Journal of Information and Management Science，2010(b)，21(12):177－195. [9] SHABTAY D，STEINER G.Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine [J].Manufacturing and Service Operations Management，2007b，9(3):332－350. [10] CHENG T C E.Optimal single machine sequencing and assignment of common due－date，Computers and Industrial Engineering，1992，22:115－120. [11] MOSHEIOV G，ORON D.Job－dependent due－window assignment based on a common flow allowance[J].Foundations of computing and Decision Sciences，2010，35:185－195. [12] SHABTAY D，STEINER G.The single－machine earliness－tardiness scheduling problem with due date assignment and resource－dependent processing times[J].Annals of Operations Research，2008，159(1):25－40. [13] WU Y B，WAN L，WANG X Y.Study in due－window assignment scheduling based in common flow allowance[J].International Journal of Production Economics，2015，165:155－157. 责任编辑:时 凌 Single Machine Scheduling with Maintenance Intervals for Processing Time CHENG Yaoling1，LIU Bingfang2 This paper considers single－machine scheduling a dereriorating maintenance activity with time. The actual processing time is a linear function of the starting time.The workpiece needs to be maintained in the process of maching，and can not be processed during maintenance.After maintenance，the processing speed of the machine is changed.The goal is to determine the location of the maintenance，so that the objective function is minimized. single machine scheduling；maintenance；proccessing time O223 A 1008－8423(2017)01－0056－03 10.13501/j.cnki.42－1569/n.2017.03.013 2016－11－15. 陈耀宁(1992－)，男，硕士生，主要从事系统理论的研究.
3 问题的算法
4 结论
(1.School of Mathematics Science，Chongqing Normal University，Chongqing 401331，China；2.School of Educational Science，Chongqing Normal University，Chongqing 401331，China)
