带有多次维修的多窗口单机排序

陈耀宁

（重庆师范大学数学科学学院，重庆401331）

带有多次维修的多窗口单机排序

陈耀宁

（重庆师范大学数学科学学院，重庆401331）

讨论了工件加工时长退化及维修区间与加工时间有关的多次维修的单机排序.工件的实际加工时间与其所在组前面工件的加工时长有关，维修区间长度与前一组的加工时长线性相关.每次维修后机器都能恢复到最原始的状态.目标是极小化最大完工时间，并在此基础上极小化时间费用函数.最后给出该问题的多项式时间算法.

单机排序；多次维修；组平衡原则；多窗口

退化效应或者学习效应［1］是因为工件的实际加工时间与工件的开始加工时间或者加工位置相关.退化效应多是因为机器在加工工件的过程中逐渐磨损而使得位置越靠后的工件的加工时间越长，学习效应与之正好相反，是因为在加工工件的过程中效率越来越高.

实际的工业生产中，机器加工一段时间后，为了保持机器的工作效率需要对机器进行维修，维修期间机器将不能进行加工任何工件，而且维修不止一次.Lee和Leon［2］首先将维修活动引入到排序问题中，并且讨论了单机排序中一些经典的目标函数.Sidney［3］首先提出了带有工期窗口指派的单机排序问题，其目标是找到工件的最优排序和提前与误工的最小费用.Yang和Lai［4］讨论了具有多窗口以及加工时间可变的单机排序.Fan和Zhao［5］研究了在退化维修活动下具有多工期及退化效应的单机排序问题，目标是得到最优工期、最优维修位置，是使工件的提前、误工、工期费用之和最小.谢秋莲和张新功［6］研究了带有线性位置退化及多维修区间的单机排序问题，目标是极小化最大完工时间和总完工时间的和.笔者在此基础上，讨论了具有多窗口以及加工时间可变的多次维修的单机排序问题.

1 问题描述

设有n个独立的工件｛J1，J2，…，Jn｝在单机上加工，工件在零时刻到达且加工过程不可中断.工件Jj的正常加工时间为pj.机器在工件的加工过程中由于老化因素需要进行多次维修，每次维修都能使单机恢复到最开始状态，即每次维修后机器的工作效率都和刚开始一样.由于单机在加工过程中存在磨损，所以工件的实际加工时间与工件的开始加工时间或者机器维修后到开始加工该工件的时长成线性关系.单机的维修时长与加工前面一组工件的运行时间也呈线性关系.以每次维修为一个节点，设维修次数为k，则将所有工件分为k＋1个组，每组工件都有一个共同的工期窗口［di，wi］，di和wi分别表示第i个工期窗口的开始时间与结束时间，i＝1，2，…，k＋1，Di＝wi－di表示工期窗口的大小.进一步假设任一个工期窗口不包含另外一个工期窗口.第i组工件记为Ii，该组工件个数记为ni，则，Mi表示第i次维修活动，相对应的维修时长为ti，则该单机排序的序列π＝［I1，M1，I2，M2，…，Ik，Mk，Ik＋1］，Gij表示第i组前j个工件的加工时间和，则第i次维修时间ti＝a Gini，a＞0为维修率，Gini为第i组前ni个工件的加工时长.工件Jj排在第i组第j个位置的实际加工时间pAij＝pj＋b Gij－1.Cj，Ej＝max｛0，di－Cj｝，Tj＝max｛0，Cj－wj｝分别表示工件Jj的完工时间，提前时间和误工时间.α，β，γ，δ分别表示提前，误工，工期开始时间，工期大小的时间费用，先考虑极小化最大完工时间Cmax，再考虑在此维修次数k和维修位置上，使得以下费用函数最小：

笔者研究的单机排序模型用三参数法可以表示为：

2 极小化最大完工问题

本节主要介绍1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax的主要结论.

则

引入记号wl，则当k确定时，

引理1 对于问题1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果没有维修，则所有工件按照SPT规则得到的排序是最优的.

证 若π是最优的工序，且所有的工件不是按照SPT规则排列得到的，则有两个相邻的工件Jj和Ji，有Pj＞Pi，交换两个工件的位置得到工序π‘，设工件Jj的开始加工时间为t0，工件Ji在工序π中的完工时间记为Ci，工件Jj在工序π‘中的完工时间记为C‘j，则：

工序π‘的工件Jj的完工时间与工序π的Ji的完工时间之差为：C‘j－Ci＝b（pi－pj）＜0与π为最优工序矛盾.

引理2 对于问题1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果维修次数k确定，则每组的工件个数满足组平衡原则，即n／（k＋1）#ni#n／k＋1（）＋1

证 由谢秋莲和张新功［6］定理2可知，如果维修次数k确定，每组工件个数满足组平衡原则.

引理3 对于问题1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果维修次数确定，则每组工件按SPT规则排列得到的序列最优.

证 显然，由引理1和引理2可直接得出该结论.

引理4 假设存在两个数列xi和yi，当xi和yi的大小序列正好相反时，乘积之和∑xiyi取得最小值.

证 Hardy等［7］首次对匹配算法进行阐述并给予之证明.

定理1 对于问题1｜ma，pAij＝pj＋b Gij－1，M＝k，ti＝a Gini｜Cmax，如果k确定，则存在最优序，其工件的序列按照SPT规则排列，将排好的工件依次排到每组最早的位置上，即第1个工件排到第1组第一个位置，第2个工件排到第2组第一个位置，……，第k＋1个工件排在第k＋1组第1个位置，第k＋2个工件排在第1组第2个位置，依此类推，但是将最后一个工件放在第k＋1组最后一个位置.

证 可以把wl当成工件在每个位置的加工时间权重，将其作为一个固定的序列，根据引理4，利用数学归纳法可以证明.

3 问题 1 ma，＝pj＋b Gij－1M＝k，ti＝a Ginimin Cmax：Z

引理5 给出一个排序，最优的工期窗口的开始时间di和结束时间wi都和某个工件的完工时间一致.

证 Mosheiov and Saring［8］证明了所有工件有一个共同工期时，存在最优的工期窗口的开始时间和结束时间都与某个工件的完工时间是一致的，且所有的加工过程是相互独立的.对于本问题该证明同样成立.

引理6 对于给定的I1，I2，…，Ik，Ik＋1，存在最优的工期窗口，使得di＝Cki［］，wi＝Ck‘i［］.其中，，i＝1，2，…，k＋1.且［x］表示大于或等于x的最小整数.

证 根据Mosheiov and Saring［9］的一个扰动技巧可以证明得到.

算法1：

Step1：将所有工件按SPT规则排列；

Step2：根据组平衡原则分组，按照定理1的规则将每个工件分配到对应的组里；

Step3：计算Cmax（π（k）），k＝1，2，…，n－1；

Step4：取Cmax（π（k＊））＝min｛Cmax（π（k））｜k＝1，2，…，n－1｝，则k＊为最佳维修次数.

Step5：确定每组工件工期的开始时间di和结束时间wi；

Step6：按照以上公式求Z值.

定理2 算法1的时间复杂度为O（n2log n）.

证 在step1的时间复杂性为O（nlog n），k从1到n－1的时间复杂度为O（n），所以其时间复杂度为O（n2log n）.

算例：求下列工件的最佳维修次数及其极小化最大完工时间，并在此基础上使费用函数最小.

p1＝6，p2＝4，p3＝1，p4＝4，p5＝8，p6＝10，p7＝7，p8＝9

a＝0.2，b＝0.3，α＝6，β＝9，γ＝2，δ＝4

算例分析：按SPT规则得到的排序为J3→J4→J2→J1→J7→J5→J8→J6，

此时

4 结论

研究的工件加工时间具有线性恶化效应，维修区间长度与前一组工件的加工时间和呈线性关系.找到最佳的维修次数使得工件的最大加工时间最小，并在此基础上求得最小费用函数.进一步的研究可以将维修活动与资源约束相结合，或者考虑在平行机上的多次维修问题.

［1］Bachman A，Janiak A.Scheduling jobs with position-dependent processing times［J］.The Journal of the Operational Research Society，2004，55：257－264.

［2］Lee C Y，Leon V.Machine scheduling with a rate-modifying activity［J］.European Journal of Operational Research，2001，128：119－128.

［3］Sidney J.Optimal single machine scheduling with earliness and tardiness penalties［J］.Oper.Res，1977，25：62－69.

［4］Dar-Li Yang，Chien Jung Lai，SuhJenq Yang.Scheduling problems with multiple due windows assignment and controllable processing times on s single machine［J］.Int.J.Production Economics，2014，150：96－103.

［5］Yan-Peng Fan，ChuanLI Zhao.Single machine scheduling with multiple common due date assignment and aging effect under a deteriorating maintenance activity［J］.Appl Math Comput，2014，46：51－66.

［6］谢秋莲，张新功.带有线性位置恶化及维修区间的单机排序问题［J］.重庆师范大学学报（自然科学版），2015，32（5）：32－37.

［7］Hardy G H，Littlewood J E，Polya G.Inequalities［M］.London：Cambridge University Press，1934.

［8］Mosheiov G，Saring A.A duewindow assignment problem with position dependent processing times［J］.Oper.Res.Soc，2008，59：997－1003.

［9］Mosheiov G，Saring A.Scheduling a maintenance activity and due-window assignment on a single machine［J］.Comout.Oper.Res，2009，36：2541－2545.

Single machine scheduling with multiple maintenance and multiple windows

CHEN Yaoning
（School of Mathematics Science，Chongqing Normal University，Chongqing 401331，China）

The single machine sequencing of repairing and repairing interval and processing time is discussed.The actual machining time of the workpiece is related to the machining time of the workpiece in front of the group，and the length of the maintenance interval is linearly related to the processing time of the former group.After each repair the machine can be restored to the most primitive state.The goal is to minimize the maximum completion time and minimize the time cost function on this basis.Finally，the polynomial time algorithm of the problem is given.

single machine；multiple maintenance；group balance principle；multiple windows

O223

A

1671-9476（2017）02-0028-04

10.13450／j.cnkij.zknu.2017.02.007

2016-10-09；

2016-11-11

陈耀宁（1992－），男，山西晋城人，硕士研究生，研究方向：物流与供应链管理.