带有维修活动和工件可拒绝的单机排序问题

陈 东，赵传立

（沈阳师范大学 数学与系统科学学院，沈阳 110034）

0 引 言

近年来有关交货期的排序问题已广为关注，交货期问题是指：若某个工件在交货期内完工，则不产生惩罚费用，如果工件在窗口之前或之后完工则会产生提前或延误的费用。Mosheiov等［1］研究了带有相同交货期的单机排序问题，目标函数为极小化最大完工时间。Mor等［2］提出了带有维修活动且具有相同大小交货期的单机排序问题，目标函数是极小化加权流时间的总费用。Yin等［3］研究了带有相同交货期和分批交货期成本的单机排序问题，目标是通过确定最优排序，确定工件的交货期、交货期的开始时间和大小，从而极小化总的费用和加权误工数等。

工件可拒绝是指：在所有到达的工件中，某些工件由于外界或自身的原因可能被拒绝加工，但也会产生费用，费用由拒绝工件集中对应工件的单位费用求出。Shabtay等［4］研究了带有位置权函数和工件可拒绝的单机排序问题，目标函数是极小化接受工件集和拒绝工件集产生的总费用。Zhang等［5］研究了工件可拒绝的单机排序问题，目标函数是极小化接受工件集的最大完工时间和被拒绝的工件产生的费用。Zhang等［6］研究了带有释放时间和工件可拒绝的单机排序问题，目标是极小化总的最大完工时间，极小化拒绝工件产生的总费用。Zhang等［7］研究了工件可拒绝的、无界并行批排序问题，目标是极小化总的完工时间和总的费用等。Cao等［8］研究了带有拒绝的单机排序问题，目标是极小化拒绝工件的总费用、接受工件的最大完工时间。

另外，为了提高机器的工作效率，缩短工件的加工时间，维修活动已被广度应用。Yang等［9］研究了带有松弛交货期、学习效应和维修活动的单机排序问题，目标是确定最优排序、最优维修位置、极小化总的费用等。Mosheiov等［10］研究了带有退化维修的单机排序问题，目标是极小化最大完工时间和总的费用等。Yang［11］研究了带有学习效应和多维修活动的单机排序问题，目标是确定最优维修位置和最优维修频率等。Yang等［12］研究了维修活动是位置线性函数的单机排序问题，目标是通过确定最优位置，极小化总的完工时间等。张丽华等［13］研究了一类单机维护调度问题研究。崔苗苗等［14］针对处理机具有一个不可用区间情况进行了研究。

本文考虑带有交货期、维修活动和工件可拒绝的单机排序问题。我们给出了一些最优解的讨论，证明了该问题是多项式时间可解的。

1 问题描述

接受工件的总费用包括提前、延误、交货期的开始时间和交货期大小产生的费用。设α≥0，β≥0，γ≥0和δ≥0分别表示提前完工时间、延误完工时间、交货期的开始时间和交货期大小的单位费用。

因此接受工件集的费用可以表示为：

拒绝工件集的费用可以表示为：

总的费用为：于是，用三参数法Graham等［15］可以表示如下：

2 先前的结论

Mosheiov［1］给出的一些性质可以应用到本文中的接受工件集，设接受工件集A中有h个工件，对于任意给定的排序A：σ＝（J1，J2，…，Jh），有如下性质：

性质1 如果C［j］＜，则C［j－1］＜。

性质2 如果C［j］＞，则C［j－1］＞。

性质3 在最优排序σ＊＝（J［1］，J［2］，…，J［n］）中，存在某个k和l，使得

其中，k＊，l＊为性质3中k，l的最优值。

性质5 对于任意给定的排序，若是最优排序，一定满足以下一种：

1）无维修活动；

2）维修活动从t＝0时刻开始；

3）维修活动的开始时间等于排在第i个位置的工件的完工时间，其中i≥l，即：维修活动一定排在某一延误工件之前。

3 最优排序

情况1 假设所有的工件都被接受，即h＝n，A＝（J［1］，J［2］，…，J［n］），此种情况已被文献［1］提到。

情况2 假设部分工件被接受，即1≤h＜n，A＝（J［1］，J［2］，…，J［h］），此时总的费用为：

现在，考虑维修活动的后2种情况：

2）维修活动在t＝0时刻开始

工件J［j］的实际加工时间为θ［j］p［j］，j＝1，2，…，h。

表示在排序σ中排在第j个位置上的工件的位置权。

可以将式子（4）化为如下指派问题：

得到式（3）的最优解。

定理1 若维修活动从t＝0时刻开始，问题

可以化为指派问题（6），在O（n4）时间内可解。

证明 对于任意给定的h，若维修活动从t＝0时刻开始，问题

在O（n3）时间内可解，因为1≤h＜n，所以该问题可以化为指派问题（6），在O（n4）时间内可解。证毕。

3）维修活动的开始时间等于工件J［i］的完工时间

其中，w［j］可应用式（5）求出。

可以将式（7）化为如下指派问题：

对于任意给定的h和i，以上指派问题在O（n3）时间内可解。由于i，h＝1，2，…，n，多次运用以上指派算法，求得的最小值便是最优值。

可以化为指派问题（8），在O（n5）时间内可解。

证明 对于任意给定的h和i，维修活动的开始时间等于工件J［i］的完工时间，其中l≤i≤h，问题1

4 结 语

本文讨论了带有交货期、维修活动和工件可拒绝的单机排序问题。将所有工件分为2个集合：分别是接受工件集和拒绝工件集。为了减少工件的加工时间，对机器进行一次拥有固定时间的维修活动。目标函数是确定被接受工件的最优排序，极小化接受工件和拒绝工件的总费用。证明了这个问题在多项式时间内可以求解。对于工件可拒绝问题的其他类型目标函数，以及其他类型的交货期问题，还有待进一步讨论。

［1］MOSHEIOV G，SARIG A.Scheduling with a common due－window：Polynomially solvable cases［J］.Inform Sciences，2010，180（8）：1492－1505.

［2］MOR B，MOSHEIOV G.Scheduling a maintenance activity and due－window assignment based on common flow allowance［J］.Int J Prod Econ，2012，135（1）：220－230.

［3］YIN Yunqiang，CHENG T C E，WANG Jiayin，et al.Single machine common due window assignment and scheduling to minimize the total cost［J］.Discrete Optim，2013，10（1）：42－53.

［4］SHABTAY D，GASPAR N，YEDIDSION L.A bicriteria approach to scheduling a single machine with job rejection and positional penalties［J］.J Comb Opt，2012，23（4）：395－424.

［5］LU Lingfa，ZHANG Liqi，NG C T.Optimal algorithms for single machine scheduling with rejection to minimize the makespan［J］.Int J Prod Econ，2011，130（2）：153－158.

［6］ZHANG Liqi，LU Lingfa，YUAN Jinjiang.Single machine scheduling with release dates and rejection［J］.Eur J Oper Res，2009，198（3）：975－978.

［7］ZHANG Liqi，LU Lingfa，NG C T.The unbounded parallel－batch scheduling with rejection［J］.J Oper Res Soc，2012，63（3）：293－298.

［8］CAO Zhigang，ZHANG Yuzhong.Scheduling with rejection and non－identical job arrivals［J］.J Syst Sci Complex，2007，20（4）：529－535.

［9］YANG Suhjenq，HSU Choujung，YANG Darli.Single－machine scheduling and slack due－date assignment with aging effect and deteriorating maintenance［J］.Optim Lett，2012，6（8）：1862－1873.

［10］MOSHEIOV G，SIDNEY J B.Scheduling a deteriorating maintenance activity on a single machine［J］.J Oper Res Soc，2010，61（5）：882－887.

［11］YANG Suhjenq.Single－machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi－maintenance activities consideration［J］.Comput Ind Eng，2012，62（1）：271－275.

［12］YANG Suhjenq，YANG Darli.Minimizing the makespan on single－machine scheduling with aging effect and variable maintenance activities［J］.Int J Manag Sci，2010，38（6）：528－533.

［13］张丽华，涂菶生.一类单机维护调度问题研究［J］.系统工程，2004，11（22）：102－105.

［14］崔苗苗，赵玉芳，王松丽.机器具有可用性限制的加权总完工时间问题［J］.沈阳师范大学学报：自然科学版，2012，30（2）：157－163.

［15］GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling：a survey［J］.Ann Discrete Math，1979，5：287－326.