带有学习效应和加工时间可控的排序问题

范雁鹏，赵传立

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

在现实生活中，工件的加工时间会由于学习效应现象或增加一些额外的资源而发生变化［1－7］。Vickson［4］首先提出了关于加工时间可控的排序模型。Choia等［5］研究了带有可控加工时间和可控释放时间的单机排序问题。Wang等［6］介绍了带有恶化工件的加工时间可控的排序问题。Shabtay等［7］提供了一个关于带有可控加工时间的排序问题的综述。关于工期指派的排序问题受到了许多研究者的关注［8－11］。在一些近期的文献中，关于交货期窗口的排序问题备受关注。Meng等［12］研究了带有恶化工件的交货期窗口问题。Mosheiov等［13］提出了每个工件均有一个不同的交货期窗口的单机排序问题。Mor等［14］在此基础上增加了一次维修活动，对3种不同的维修情况分别作了详细分析。Yin等［15］考虑了加工时间可控的多窗口单机排序问题。

本文考虑文献［13］和文献［15］的排序模型，将加工时间可控，学习效应与多窗口的排序问题相结合，目标是确定最优排序和最优资源分配量。

1 问题描述

给定一台机器和一个工件集N＝｛J1，J2，…，Jn｝。设pj，Cj分别表示工件Jj的实际加工时间和完工时间。本文考虑如下的2种不同加工时间模型：

每个工件Jj均有一个交货期窗口］≤。工件Jj的窗口开始时间定义为＝pj（uj）＋q1，其结束时间定义为＝pj（uj）＋q2（q2≥q1）。D＝q2－q1表示工件Jj的窗口的大小，则所有工件的窗口大小相同。Ej＝max｛0，－Cj｝表示工件Jj的提前，若Cj＞，则Uj＝1；否则Uj＝0。Cmax＝maxj＝1，…，nCj表示最大完工时间。α≥0，γ≥0，δ≥0，θ≥0分别表示提前，窗口开始时间，窗口大小和最大完工时间的单位费用。vj≥0表示资源分配量的单位费用，若工件Jj延误，则βj表示误工的单位惩罚。目标是极小化总费用函数

对于给定的任意一个排序π，［j］表示排在位置j上的工件，设E＝｛Jj∈N｜Cj＜｝，W＝｛Jj∈N｜≤Cj＜｝，O＝｛Jj∈N｜Cj＝｝，T＝｛Jj∈N｜Cj＞｝

运用三参数表示法，本文所考虑的问题可分别表示为：

2 线性资源函数

对于问题1，由文献［15］，可以得到以下引理：

引理1［15］最优排序满足以下性质：

1）所有工件均连续加工，机器无空闲状态且第一个工件在零时刻开始加工。

2）若Cj≤，则Cj－1≤；若Cj＞，则Cj＋1＞。

3）q1的最优值等于C［k＊－1］，q2的最优值等于C［l＊－1］，其中k＊≤l＊≤n，k＊＝max｛n（δ－γ）／α，0｝。

4）目标函数可以表示为：

引理2［15］最优排序满足：

其中：m1是满足min｛n（γ＋），nδ＜βj｝的工件数；m2是满足min｛nγ，nδ｝＞βj的工件数。

根据式（4），将式（1）代入式（3），目标函数可表示成如下形式：

因此，最优资源分配量可以表示为：

对于1≤i，j≤n，设

此外，设yij是一个0／1变量，若工件Jj排在位置i上，则yij＝1；否则yij＝0。因此，问题1可归结为如下指派问题：

显然，指派问题（11）可以在O（n3）时间内解决。

由以上分析可知，问题1可以通过如下算法求得最优排序。

算法1

步骤1 置Z＊＝＋∞，运用引理2计算和，置l＝

步骤2 当l≤¯l，执行

步骤2.1 运用式子（10）计算Cij（l）；

步骤2.2 通过解决指派问题（11）来确定最优排序，记最优排序为π＊（l）＝（J［1］，J［2］，…，J［n］），极小化总费用Z（l）；

步骤2.3 若Z（l）＜Z＊，则置Z＊＝Z（l），l＊＝l，π＊＝π＊（l）；

步骤2.4 置l＝l＋1。

步骤3 运用式（7）计算最优资源分配量。

步骤4 运用式（1）计算最优加工时间。

定理1 问题1通过算法1求得最优排序，计算复杂性为O（n4）。

证明 对于一个给定的l，解决指派问题（11）需要的时间是O（n3），步骤2至多需要O（n）次迭代；步骤1，步骤3和步骤4均可以在线性时间内解决。因此，算法1的整体计算复杂性为O（n4）。证毕

3 凸资源函数

其中Wj（l）由式（6）决定。

引理3 对于一个给定的l，问题2的最优资源分配量

将式（2）代入式（3），目标函数可以表示成如下形式：

根据式（4），将式（13）代入式（12），对于一个给定的l，目标函数可以表示为：

引理4 对于任意给定的资源分配量u，最优排序满足：在集合E中的全部工件按照θ［j］非增的规则排列，在集合W或T中的全部工件按照任意顺序排列。

证明 根据式（6），式（14）和式（15），若工件在集合W或T中，则目标函数值与工件所处的位置无关，即集合W或T中的工件可按任意顺序排列；若工件在集合E中，Wj（l）是一个非减函数，则ξj是非减的，因此，集合E中的工件按照θ［j］非增的规则排列。

证毕。

将全部工件按照θj非增的顺序标号。（h，i，j，k）表示集合O中工件Jh的一个状态，且集合O中只包括一个工件，i表示工件集｛1，2，…，i｝已排好，j表示在集合E中有j（0≤j≤i）个工件已排好，k表示在集合W中有k（0≤k≤i－j）个工件已排好。对于任意排序，F（h，i，j，k）表示与状态（h，i，j，k）相对应的最优值，S（h，i，j，k）表示在状态（h，i，j，k）下，F（h，i，j，k）值对应的一个排序。若这样的排序不存在，则设F（h，i，j，k）＝＋∞。

1）工件Ji被指派到集合E中：可以通过排序S（h，i－1，j－1，k）得到S（h，i，j，k），此时

2）工件Ji被指派到集合W中：可以通过排序S（h，i－1，j，k－1）得到S（h，i，j，k），此时

3）工件Ji被指派到集合T中：可以通过排序S（h，i－1，j，k）得到S（h，i，j，k），此时

由以上分析，可以得到如下的动态规划算法。

算法2

步骤1 按照θj非增的规则排列全部工件，置

步骤2 对于1≤h≤n，执行

步骤2.1 移除工件Jh。若h＜n，则按照下标递减的规则重新排列余下的工件（h＋1，…，n），得到排序1，2，…，n－1。

步骤2.2 对于1≤i≤n－1，0≤j≤i，0≤k≤i－j，计算

步骤3 最优值是

记最优排序为S＊＝（J［1］，J［2］，…，J［n］），l＊是与其对应的值。

步骤4 运用式（13）计算最优资源分配量。

步骤5 运用式（2）计算最优加工时间。

定理2 问题2可以通过算法2求得最优排序，计算复杂性为O（n4）。

证明 在F（h，i，j，k）中，至多需要n4个状态，并且每一个F（h，i，j，k）均能在常数时间内求得，因此算法2的整体计算复杂性为O（n4）。证毕。

4 结 论

本文介绍了具有学习效应和加工时间可控的交货期窗口的单机排序问题。讨论了工件的加工时间是所分配资源量的线性函数和凸函数2种情况，针对这2种情况，分别给出了多项式时间算法。

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

［2］王纯，赵传立.带有学习效应和机器可用性限制的排序问题［J］.系统工程与电子技术，2009，31（6）：1372－1375.

［3］BISKUP D.A state－of－the－art review on scheduling with learning effects［J］.Eur J Oper Res，2008，188（2）：315－329.

［4］VICKSON R G.Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine［J］.Oper Res，1980，28（5）：1155－1167.

［5］CHOIA B C，YOON S H，CHUNG S J.Single machine scheduling problem with controllable processing times and resource dependent release times［J］.Eur J Oper Res，2007，181（2）：645－653.

［6］WANG Xueru，Wang Jianjun.Single－machine scheduling with convex resource dependent processing times and deteriorating jobs［J］.Appl Math Model，2013，37（4）：2388－2393.

［7］SHABTAY D，Steiner G.A survey of scheduling with controllable processing times［J］.Discrete Appl Math，2007，155（13）：1643－1666.

［8］SHABTAY D.Due date assignments and scheduling a single machine with a general earliness／tardiness cost function［J］.Comput Oper Res，2008，35（5）：1539－1545.

［9］HSUA Choujung，YANG Suhjenq，YANG Darli.Two due date assignment problems with position－dependent processing time on a single－machine［J］.Comput Ind Eng，2011，60（4）：796－800.

［10］SHABTAY D，STEINER G.The single－machine earliness－tardiness scheduling problem with due date assignment and resource－dependent processing times［J］.Ann Oper Res，2008，159（1）：25－40.

［11］SHABTAY D，STEINER G.A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates［J］.J Scheduling，2011，14（5）：455－469.

［12］MENG Jintao，YU Jun，LU Xiaoxu.Scheduling Deteriorating Jobs with a Common Due Window on a Single Machine［J］.Information Technology，2012，11（3）：392－395.

［13］MOSHEIOV G，ORON D.Job dependent due－window assignment based on a common flow allowance［J］.Founda Comp Deci Sci，2010，35（3）：185－195.

［14］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.

［15］YIN Yunqiang，CHENG T C E，WU Chinchia，et al.Single－machine due window assignment and scheduling with a common flow allowance and controllable job processing time［J］.J Oper Res Soc，2014，65：1－13.