具有公共流、退化效应与维护和资源分配的单机窗口排序问题

赵崴羽，罗成新

(沈阳师范大学 数学与系统科学学院，沈阳 110034)



具有公共流、退化效应与维护和资源分配的单机窗口排序问题

赵崴羽，罗成新

(沈阳师范大学 数学与系统科学学院，沈阳 110034)

考虑具有公共流、退化效应与维护和资源分配的单机窗口排序问题，所有任务都具有松弛窗口。在实际加工过程中，为提高生产效率，提供给每个任务不同的资源，资源总量有限，并适时对机器进行维护，一旦维护活动结束，机器恢复到最初状态并且任务的退化效应更新。机器维护持续的时间取决于维护活动的开始时间。假定任务的实际加工时间是关于任务排序位置及资源分配的凸函数，目标是确定任务的窗口、资源分配、任务排序使得提前惩罚、延误惩罚、窗口位置、窗口宽度、时间表长、任务完工时间之和惩罚及资源消耗费用之和最小。给出一个最优算法求解该问题。

排序；退化效应；退化维护；资源分配；窗口；公共流

经典排序中，任务的加工时间是固定的常数，但在实际生产中，任务等待或机器等原因都会引起任务加工时间的增长，即任务的实际加工时间与该任务的开始加工时间有关[1]，因此，适时地对机器进行检修能提高机器的生产效率。通常情况下，给任务分配一定额度资源，任务的加工时间变小。任务获得的资源与其加工时间成反比[2-5]。

由于准时生产概念的出现，具有工期的排序问题引起广泛关注。工期问题包括所有任务共用一个工期(CON)、不同的任务具有不同的工期(DIF)、不同的任务具有不同的松弛工期(SLK)等。Mosheiov和Oron将具有公共流的松弛工期问题推广到具有公共流的松弛窗口问题。不同的任务具有不同的窗口，但所有窗口的长度相同，每个任务窗口的开始时间和结束时间分别等于任务的实际加工时间加上公共流和。如果任务在窗口之前加工完成会引起提前惩罚，如果任务在窗口之后加工完成将导致延误惩罚，只有任务在窗口内加工完成才不会引起惩罚。根据准时生产理论，任务的提前完成或者延误完成都是不被鼓励的。文献[4]研究具有公共流q1和q2可控加工时间的单机窗口问题，文献[5]研究了具有公共流、学习效应和资源分配的单机窗口排序问题，目标是得到最优公共流、最优窗口长度、最优资源分配和最优排序使得提前惩罚费用、延误惩罚费用、窗口的开始时间和长度费用、时间表长和加权资源费用之和最小。文献[6]研究带有凸资源加工时间模型的排序问题，目标是得到最优排序和资源分配使得提前惩罚费用、延误惩罚费用和窗口开始时间费用之和最小。

本文将文献[5]研究的问题拓展到具有维护活动和资源约束的环境下，考虑具有公共流、退化效应与维护和资源分配的单机窗口排序问题，目标是确定最优公共流、最优窗口长度、最优资源分配、最优维护位置、最优排序使得提前惩罚、延误惩罚、窗口位置、窗口宽度、时间表长、任务完工时间之后惩罚及资源消耗费用之和最小，并给出了多项式时间算法。

1 问题描述

给定n个独立任务J={J1,J2,…,Jn}，在零时刻已全部到达，所有任务加工不可中断，在一台机器上进行加工。考虑凸函数模型：

(1)

(2)

2 预备知识

显而易见，最优排序π*中，第一个任务从零时刻开始加工，在两个相邻的加工任务中间无空闲时间。

引理 3 任意给定排序π及资源u=(u1,…,un)，存在最优的q1、q2分别为第k个、第l个任务的完工时间(l≥k)，即q1=p[1]+…+p[k]，q2=p[1]+…+p[k]+…+p[l]。

证明 与文献[13]中证明相似，证完。

引理 4 在最优排序中，q1=C[k]，k=⎣n(δ-γ)/α」；q2=C[l]，l=⎣n(β-δ)/β」；这里⎣x」表示不大于x的最大整数。

3 最优解

当维护活动在第k个任务之前的某一位置进行，1≤i≤k，由引理3和引理4，得到

当维护活动在第k个任务与第l个任务之间的某一位置进行，k

当维护活动在第l个任务之后的某一位置进行，l≤i≤n，得到

当1≤i≤k时，记W=αib+γnb+ηb+λ(n-i)b，

(3)

当k

(4)

当l≤i≤n时，记W=β(n-i)b+ηb+λ(n-i)b，

(5)

(6)

φ为拉格朗日乘子。求上式关于变量(u[j],φ)的一阶偏导数，令其为零有

(7)

(8)

(9)

(11)

(12)

通过(7)、(10)、(11)和(12)，得到最优资源分配为

(13)

将(13)带入到目标函数Z中，得到

(14)

为了得到所求问题的最优排序，将所求问题转化为指派问题，令yjr为0/1变量，当任务Jj排在第r个位置上加工时，yjr=1，否则，yjr=0。指派问题如下

算法1

第一步 通过引理4，计算q1和q2的最优位置。

第三步 由(13)计算最优资源分配，由(1)计算最优加工时间。

定理1 利用算法1该排序问题可在O(n4)时间内求出最优解。

证明 上述分析保证了结论的正确性。第一步、第三步和第四步均可在O(1)时间内求解，第二步可在O(n3)时间内求解，维护位置i固定后，该排序问题转化为指派问题求解，故该排序问题可在O(n3)时间内求解该问题。维护可以在n个位置上进行，因此该问题可在O(n4)时间内可解。证完。

4 实例

某次生产中有3个任务待加工，任务的正常加工时间和退化因子如表1所示。

表1 任务数据表

j123pj451830aj0．30．50．25

其他参数分别为：α=12，β=10，γ=5，δ=6，η=1，λ=0.5，θ=0.8，k=1，b=18，c=0.8。求最优流容量、最优窗口长度、最优资源分配、最优排序使得(2)最小。

[1]PINEDO M.Scheduling:Theory,Algorithms and Systems[M].Englewood cliffs,NJ.2012,Prentice hall.

[2]YIN Y,CHENG T C E,WU,et al.Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times[J].International Journal of Production Research,2013,51(17):5083-5099.

[3]YANG D L,CHENG T C E,YANG S J.Parallel-machine Scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions[J].International Journal of Production Research,2014,52(4):1133-1141.

[4]Y YIN,TCE CHENG,C C WU,et al.Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time[J].Journal of the Operational Research Society,2014,65(1):1-13.

[5]GANG LI,MEILING LUO,WENJIE ZHANG,et al.Single machine due-window assignment scheduling based on common flow allowance,learning effect and resource allocation[J].International Journal of Production Research,2015,53(4):1228-1241.

[6]JIBO WANG,JIANJUN WANG.Research on scheduling with job-dependent learning effect and convex resource-dependent processing times[J].International Journal of Production Research,2015,53(19):5826-5836.

[7]MOSHEIOV G,D ORON.Job-dependent due-window assignment based on a common flow allowance[J].Foundations of Computing and Decision Sciences,2010,35:185-195.

[8]MOR B,G MOSHEIOV.Scheduling a maintenance activity and due-window assignment based on common flow allowance[J].International Journal of Production Economics,2012,135(1):222-230.

[9]GRAHAM R L,LAWLER E L,LENSTRA J K,et al.Optimization and approximation in deterministic sequencing and scheduling[J]:A survey.Annals of Discrete Mathematics,1979,5(1):287-326.

[10]YANG S J,YANG D L,CHENG T C E.Single-machine due-window assignment and scheduling with job-dependent aging effects and deterioration maintenance[J].Comput.Oper.Res,2010，37(8):1510-1574.

[11]MIN JI,JIAOJIAO GE,KE CHEN,et al.Single-machine due-window assignment and scheduling with resource allocation,aging effect,and a deteriorating rate-modifying activity[J].Computers&Industrial Engineering,2013,66:952-961.

[12]MOSHEIOV G,SARIG A.Scheduling a maintenance activity and due-window assignment on a single machine[J].Comput.Oper.Res,2009,36(9):2541-2545.

[13]WANG J B,L LIU,C WANG.Single machine SLKDIF due window assignment problem with learning effect and deteriorating jobs[J].Applied Mathematical Modelling,2011,35(8):4017-4022.

[14]YANG S J,YANG D L,CHENG T C E.Single-machine due-window assignment and scheduling with job-dependent aging effects and deterioration maintenance[J].Comput.Oper.Res,2010,37(8):1510-1574.

[15]WANG J B,M Z WANG.Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time[J].Computers & Operations Research,2012,39(3):492-497.

(责任编辑：吴萍 英文审校：刘勇进)

A Single-machine due-window assignment scheduling based on common flow allowance with deteriorating effect,maintenance activity and resource allocation

ZHAO Wei-yu,LUO Cheng-xin

(School of Mathematics and Systems Science,Shenyang Normal University,Shenyang 110034,China)

This paper considered a single-machine due-window assignment scheduling problem based on a common flow allowance.In order to improve production efficiency,a budget of resource is assumed to be finite.Once the maintenance activity has been completed,the machine will revert to its initial condition and the aging effect will start anew.The maintenance duration depends on its starting time.We assumed the actual processing time of a job was a convex function of its position and resource allocation.The objective was to find the common flow allowance,the due-window size,the resource allocation and the job sequence which minimizes the total cost of earliness,tardiness,the starting time of due-window,the size of due-window,makespan,the total of completion time of all jobs,and resource allocation.We introduce an efficient algorithm to solve the problem.

scheduling；aging effect；maintenance activity；resource allocation；due-window；common flow allowance

2016-06-28

国家自然科学基金(项目编号：11171050);辽宁省教育厅项目(项目编号：L2014433)

赵崴羽(1992-)，女，辽宁朝阳人，硕士研究生，主要研究方向：组合最优化与随机运筹学，E-mail:zwy_house@qq.com；罗成新(1958-)，男，辽宁新宾人，教授，主要研究方向：组合最优化与随机运筹学，E-mail:luochengxin@163.com。

2095-1248(2016)05-0082-06

O223

A

10.3969/j.issn.2095-1248.2016.05.015