加工时间依赖与位置有关的负荷和资源的工期指派问题

张浩楠，罗成新

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

基础科学与工程

加工时间依赖与位置有关的负荷和资源的工期指派问题

张浩楠，罗成新

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

讨论了带有公共工期且加工时间依赖与有关的位置负荷和资源的单机排序问题。工件的加工时间是一个和资源分配、工件在排序中的位置以及负荷有关的凸函数，所有任务具有一个公共工期。目标是确定最优工期的位置、分配给每个工件的资源和最优的工件排序，使由提前、误工、工期、资源分配构成的总费用最小化。应用指派问题解法给出了时间复杂度为O(n3)的最优算法。

单机排序；资源分配；可控加工时间；依赖位置的负荷；工期

近年来，带有资源分配和工期指派的单机排序问题倍受关注。在传统的排序问题中，工件的加工时间是一个常数。然而在实际环境中，工件的加工时间可能是一个和资源分配、工件在排序中位置有关的函数，由此产生一些新型排序问题。Wang D等[1]考虑了带有资源分配和学习效应的单机排序问题并给出多项式算法。Lu Y-Y等[2]研究了带有资源分配的单机排序问题。王吉波等[3]考虑了具有恶化工件的不同工期指派问题，证明该问题的算法复杂性是多项式时间可解的，并给出了如何求解该问题的最优算法。Wang J-B等[4]研究了带有公共工期、资源分配以及学习效应的单机指派问题。郭玲等[5]讨论了带有公共交货期窗口和工件的加工时间可控的单机排序问题，给出了最优解的一些性质，并且证明了这个问题是多项式时间可解的。Mosheiov G[6]研究了带有学习效应的排序问题。王洪芳等[7]研究单机排序下加工时间可变的工期窗口指派问题,任务的加工时间是关于所获资源分配量的一个凸函数，证明了此问题是多项式时间可解的,并给出了最优算法。He H等[8]研究了带有资源约束和标准截断学习效应的排序问题。Ng CT等[9]考虑了带有几种公共工期和资源分配的单机排序问题。王吉波等[10]研究了具有学习效应的单机可控加工时间排序问题，其中工件的加工时间是其所在位置的函数，且与加工时间的控制变量有关，并证明他们都能转化为指派问题，从而多项式时间可解。此外，Seidmann A等[11]研究了工期指派的排序问题。Gordon V等[12]考虑了公共工期指派的单机排序问题。Shabtay D等[13]研究了可控加工时间的排序问题。

上述文献大多数没有提到负荷，负荷是与工件本身及位置有关的参数，而工件的加工时间是一个和负荷有关的凸函数，但关于负荷的排序问题的研究很少。Oron D[14]考虑了可控加工时间与位置有关负荷的单机排序问题，他所假定的模型中不含有工件的工期。然而在实际的生产过程中，顾客需要在一定时间内获得产品，没有按时完成或提前完成可能会产生一定的费用，这样就产生了带有工期指派的排序问题。本文考虑的是加工时间依赖与位置有关的负荷、资源的工期指派的单机排序问题。所有任务具有一个公共工期(是决策变量)。目标是确定最优工期的位置、分配给每个工件的资源和最优的工件排序，使由提前、误工、工期、资源分配构成的总费用最小化。应用指派问题解法给出了时间复杂度为O(n3)的最优算法。

1 问题描述

设有n个独立的工件J={J1,J2,…,Jn}在一台机器上加工，所有的工件在零时刻都已到达，且加工不可中断，机器在每个时刻至多加工一个工件。假设当工件Jj排第r个位置上加工时，它的实际加工时间为

其中参数wjr是与工件本身及位置有关的任务负荷，h>0，uj为分配给Jj的资源，工件Jj的资源uj的单位费用为vj，所有工件有一个公共工期d。工件Jj的提前和误工分别为Ej=max{0,d-Cj}和Tj={0,Cj-d}，其中Cj表示工件Jj的完工时间。给定每个工件一个固定的资源，那么相应地它的加工时间也被确定，因此目标是确定工期d的最优位置，分配给每个工件的资源u*={u1,u2,…,un}和最优的工件排序，使得下面的目标函数最小。

其中α>0,β>0,δ>0,vj>0是给定的常数，分别表示提前、误工、工期和资源的单位费用。

本文考虑的是有公共工期的单机排序问题。利用三参数表示法(Graham R L,Lawler E L, Lenstra J K，et al[15])，此排序问题可记为

2 初步分析

引理1 任意给定一个排序π，存在最优的工期d与某一个工件的完工时间是一致的。

证明 设给定的任务排序，π=[J[1],J[2],…,J[n]]

设C[k-1]

其中

A=[α(k-1)-β(n-k+1)+nδ]

A,B与Δ无关，为使得目标函数Z最小，则当A≥0时，取Δ=0；当A<0时，取Δ=p[k]k(u[k])。工期d与某一个工件的完工时间是一致的。引理1证毕。

证明 由引理1我们知道最优的工期d与某一个工件的完工时间是一致的，令这一工件的角标为J[k]，其中1≤k≤n，其相应的最优的目标函数为f(C[k],π)。

对任意有σ>0，有f(C[k]+σ)-f(C[k],π)≥0。工期由C[k]变为C[k]+σ，工期和提前的费用至少增加σ(nδ+kα)，误工的费用减少了σ(n-k)β。

3 排序问题的最优解

由引理1、引理2可知工期d*=C[k]被确定。所以，提前完工的工件为J[1],J[2],…,J[k-1]，误工的工件为J[k+1],J[k+2],…,J[n]。

u[r]*=

(1)

证明

(2)

将式(2)对u[r]求偏导：

将最优资源表达式(1)带入目标函数,可得

令xjr为0/1变量，当工件Jj排在第r个位置加工时xjr=1，否则xjr=0。问题可以由以下指派问题求解。

(3)

(4)

(5)

xjr∈{0 , 1}j,r=1,2,…,n

(6)

(7)

其中j=1,2,…,n，基于上述分析，给出下述最优算法。

算法1

第一步：输入α,β,δ,vj,h,n,wjr；

第三步：求解指派问题式(3)-式(6)得到最优任务排序。π*=[J[1],J[2],…,J[n]]；

第五步：求出d*=C[k]，再由(2)计算最优目标函数值。

定理1 算法1可在O(n3)内求出问题1

表1 例1中wjr的值

表2 例1中λjr的值

4 结论

本文考虑的是加工时间依赖与位置有关的负荷、资源的工期指派的单机排序问题。所有任务具有一个公共工期，目标是确定最优工期的位置、分配给每个工件的资源和最优的工件排序，使由提前、误工、工期、资源分配构成的总费用最小化。应用指派问题解法给出了时间复杂度为的最优算法。

[1]WANG D,WANG M-Z,WANG J-B.Single-machine scheduling with learning effect and resource-dependent processing times[J].Computers & Industrial Engineering,2010,59(3):458-462.

[2]LU Y-Y,LI G,WU Y-B.Optimal due-date assignment problem with learning effect and resource-dependent processing times[J].Optimization Letters,2014,8(1):113-127.

[3]王吉波，刘璐，许扬涛，等.具有恶化工件的不同工期指派问题研究[J].沈阳航空航天大学学报，2013,30(5):83-87.

[4]WANG J-B,WANG M-Z.Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times[J].Asia Pacific Journal of Operational Research,2014,31(5):1450036-1-1450036-15.

[5]郭玲,赵传立.带有公共交货期窗口和加工时间可控的单机排序问题[J].重庆师范大学学报:自然科学版,2012,29(6):9-14.

[6]MOSHEIOV G.Scheduling problems with a learning effect[J].European Journal of Operational Research,2001,132(3):687-693.

[7]王洪芳,罗成新.资源约束下加工时间可变的工期窗口指派问题[J].沈阳师范大学学报(自然科学版),2015,33(4):482-487.

[8]HE H,LIU M,WANG J-B.Resource constrained scheduling with general truncated job-dependent learning effect[J].Journal of Combinatorial Optimization,December,2015:1-19.

[9]NG CT,CHENG TCE,KOVALYOV MY,et al.Single machine scheduling with a variable common due date and resource-dependent processing times[J].Computers & Operations Research,2003,30(8):1173-1185.

[10]王吉波,汪佳,牛玉萍.具有学习效应的单机可控加工时间排序问题研究[J].沈阳航空航天大学学报,2014,31(5):82-86.

[11]SEIDMANN A,PANWALKAR S S,SMITH M L.Optimal assignment of due-dates for a single processor scheduling problem[J].International Journal of Production Research,2010,19(4):393-399.

[12]GORDON V,PROTH J M,CHU C.A survey of the state-of-the-art of common due date assignment and scheduling research[J].European Journal of Operational Research,2002,139(1):1-25.

[13]SHABTAY D,STEINER G.A survey of scheduling with controllable processing times[J].Discrete Applied Mathematics,2007,155(13):1643-1666.

[14]ORON D.Scheduling controllable processing time jobs with position-dependent workloads[J].International Journal of Production Economics,2015,173:153-160.

[15]GRAHAM RL,LAWLER EL,LENSTRA JK,et.al.Optimization and approximation in deterministic sequencing and scheduling.a survey[J].Ann Discret Math,1979,5(1):287-326

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

Due-date assignment problem with position-dependent workload and resource processing times

ZHANG Hao-nan,LUO Cheng-xin

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

We consider a common due-date assignment and single machine scheduling problem in which job processing time has position-dependent workload.Under the condition that the processing time of a job is a convex function of the amount of a resource allocated to it and its position in the processing sequence and workload,all jobs have a common due-date.The objective is to find the optimal due-date,the optimal resource allocation scheme and the optimal job sequence to minimize the total cost,which involves earliness,tardiness,due-date,and resource consumption.We proposed an efficientO(n3) algorithm to solve this assignment problem.

single machine scheduling;resource allocation;controllable processing times;position-dependent workload;due-date

2016-10-24

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

张浩楠(1993-),女,辽宁锦州人,硕士研究生，主要研究方向：组合最优化,E-mail:zhnagnes@foxmail.com；罗成新,(1958-),男,辽宁新宾人,教授，主要研究方向：组合最优化，E-mail:luochengxin@163.com。

2095-1248(2017)01-0091-06

O223

A

10.3969/j.issn.2095-1248.2017.01.014