Operations Research and Fuzziology
Vol. 10  No. 01 ( 2020 ), Article ID: 33685 , 6 pages
10.12677/ORF.2020.101003

Slack Due Date Assignment Scheduling Problem Based on Learning and Deterioration Effect

Xun Xi, Xiaona Sun, Chong Wang, Hui Xu, Honglin Pan, Jibo Wang*

School of Science, Shenyang Aerospace University, Shenyang Liaoning

Received: Dec. 6th, 2019; accepted: Dec. 20th, 2019; published: Dec. 30th, 2019

ABSTRACT

This paper considers a scheduling problem with learning and deterioration effect; under a single machine and slack due date assignment, our objective is to determine the schedule of jobs and the common slack flow in order to minimize the linear combination of the just-in-time cost (including the earliness, tardiness and common slack flow) and makespan . The properties of the optimal solution are given, and then we prove that the problem can be solved in polynomial time.

Keywords:Scheduling, Deterioration Effect, Learning Effect, Due Date Assignment, Single-Machine

基于学习与恶化效应的松弛工期指派 排序问题

奚汛,孙晓娜,王崇,徐卉,潘红霖,王吉波*

沈阳航空航天大学理学院,辽宁 沈阳

收稿日期:2019年12月6日;录用日期:2019年12月20日;发布日期:2019年12月30日

摘 要

研究工件加工时间同时具有学习与恶化效应的排序问题,在一台机器和松弛工期指派下,目标是确定工件的加工顺序和松弛工期的共同松弛流使得工件的准时制成本(包括提前时间,延误时间和共同松弛流)和最大完工时间的线性组合最小。对此问题给出了最优解满足的性质,从而证明了此问题是多项式时间可解的。

关键词 :排序,恶化效应,学习效应,工期指派,单机

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在实际的生产过程中,工件的加工时间可能与工件所排位置和其开始加工时间有着某种联系,即工件具有学习和恶化效应。学习效应产生的背景是工件的加工时间会随着机器(比如技术工人)熟练度的提升、机器磨合度的增加等因素而使后来加工的工件实际加工时间变短(Biskup [1],王吉波等 [2],王雪茹等 [3] )。恶化效应产生的背景是在钢铁制造业,钢坯在加工的过程中需要温度的限制,如果钢坯不能马上加工,即需要等待,则它的温度会降低,从而导致开始加工时间越晚,加工时间越长(Gawiejnowicz [4],王吉波等 [5],王吉波和赵伯来 [6] )。Lee [7] 首次考虑了工件同时具有学习与恶化效应的排序问题,即工件 J i 的实际加工时间为 p i A = α i t r b p i A = ( a 0 + α i t ) r b i = 1 , 2 , , n ,其中 α i 为工件 J i 的恶化率, a 0 为正常加工时间,r为工件所排的位置, b 0 为所有工件的学习因子,t为工件 J i 的开始加工时间。在单机情况下,他证明了一些正则目标函数是多项式时间可解的。Wang [8] 也考虑了工件同时具有学习与恶化效应的排序问题,即工件 J i 的实际加工时间为 p i A = ( a i + α t ) r b ,其中 a i 为工件的正常加工时间, α 0 为恶化率。在单机情况下,他证明了最大完工时间和总完工时间极小化问题都是多项式时间可解的,加权总完工时间和最大延误极小化问题在一些特殊情况下是多项式时间可解的。在流水作业情况下,他对一些特殊情况,证明了最大完工时间、总完工时间,加权总完工时间和最大延误极小化问题也都是多项式时间可解的。Yang和Kuo [9] 考虑了工件同时具有学习与恶化效应的排序问题,即工件 J i 的实际加工时间为 p i A = a i r b i + α t ,其中 b i 0 为工件 J i 的学习因子。他们证明了一些正则和非正则目标函数是多项式时间可解的。

最近,王吉波等 [10] 研究了同文献 [9] 一样的加工时间模型,在工件具有共同工期(CON)指派下,他们证明了在共同工期指派下的独立位置权重问题是多项式时间可解的。在准时制生产模式下,比较重要的工期指派模型有三类,即共同工期指派模型,松弛工期(SLK)指派模型(参见Liu等 [11] )和不同工期指派模型(参见王吉波等 [12] )。本文考虑在松弛工期指派模型下,工件加工时间具有学习与恶化效应的单机排序问题,对工件的准时制成本和最大完工时间的线性组合最小问题给出了最优解满足的性质,并证明这个问题也是多项式时间可解的。

2. 问题描述

n个工件 J = { J 1 , J 2 , , J n } 要在一台机器上加工,同一时刻这台机器最多加工一个工件,且不允许中断。假设工件 J i 的正常加工时间为 a i ,则工件 J i 的实际加工时间为

p i A = a i r b i + α t , i = 1 , 2 , , n ,

其中r为工件所排的位置, b i 0 为工件 J i 的学习因子, α 0 为恶化率,t为工件 J i 的开始加工时间。我们考虑松弛工期指派,即工件 J i 的工期为 d i = p i A + q o p t (其中 q o p t 为共同松弛流,是一个决策变量), i = 1 , 2 , , n 。令 C i 表示工件 J i 的完工时间,目标是确定一个最优排序 π = [ π ( 1 ) , π ( 2 ) , , π ( n ) ] ( π ( i ) 代表在排序中的第i个位置加工的工件)和最优的 q o p t ,使目标函数

Z ( π , q o p t ) = η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max

最小,其中 C max = max { C i | i = 1 , 2 , , n } 为最大完工时间, 0 η 1 是一个给定常数, ω i ( i = 1 , 2 , , n ) 为位置权重, ω 0 q o p t 的权重。用三参数表示法(Graham等 [13] ),我们研究的问题可表示为

1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max

Liu等 [11] 证明了工件加工时间为常数下的问题 1 | S L K , q o p t | i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t 是多项式时间可解的,下面我们证明问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max 仍然多项式时

间可解。

3. 主要结论

对于问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max ,显然存在一个最优排序,

从第一个工件开始加工到最后一个工件结束,机器加工无空闲,且第一个工件在零时刻开始加工。

引理1对于给定的序列 π = [ π ( 1 ) , π ( 2 ) , , π ( n ) ] ,决策变量 q o p t 等于某个任务的完工时间,即

q o p t = C π ( l ) = i = 0 l p π ( i ) A ,其中l是序列 ω 0 , ω 1 , , ω n 的中位数,并使下面不等式成立

j = 0 l ω j j = l + 1 n ω j , j = 0 l + 1 ω j j = l + 2 n ω j (1)

证明:与文献Liu等 [11] 的证明方法类似。

引理2问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max 的目标函数可以写为 η ( i = 1 n w i | C π ( i ) d π ( i ) | + w 0 q o p t ) + ( 1 η ) C max = i = 1 n λ i p [ i ] A ,其中

λ i = { η v = 0 i w v η + 1 , i = 1 , 2 , , l ; η v = i + 1 n ω v η + 1 , i = l + 1 , , n 1 ; 1 η , i = n (2)

证明:假设给定最优排序为 π = [ π ( 1 ) , π ( 2 ) , , π ( n ) ] q o p t = C π ( l ) ,可知

η ( i = 1 n w i | C π ( i ) d π ( i ) | + w 0 q o p t ) + ( 1 η ) C max = η ( ω 0 C π ( l ) + i = 1 l + 1 ω i ( C π ( l ) C π ( i 1 ) ) + i = l + 2 n ω i ( C π ( i 1 ) C π ( l ) ) ) + ( 1 η ) C max = η ( i = 0 l + 1 ω i v = i l p π ( v ) A + i = l + 2 n ω i v = l + 1 i 1 p π ( v ) A ) + ( 1 η ) i = 1 n p π ( i ) A = i = 1 n λ i p π ( i ) A

其中 λ i = { η v = 0 i w v η + 1 , i = 1 , 2 , , l ; η v = i + 1 n ω v η + 1 , i = l + 1 , , n 1 ; 1 η , i = n

对于给定排序 π = [ π ( 1 ) , π ( 2 ) , , π ( n ) ] ,由王吉波等 [10] 得工件 J π ( i ) 的完工时间和实际加工时间分别为

p π ( i ) A = α ( 1 + α ) i 2 a π ( 1 ) 1 b π ( 1 ) + α ( 1 + α ) i 3 a π ( 2 ) 2 b π ( 2 ) + + α ( 1 + α ) a π ( i 2 ) ( i 2 ) b π ( i 2 ) + α a π ( i 1 ) ( i 1 ) b π ( i 1 ) + a π ( i ) i b π (i)

又由引理2,可得:

Z ( π , q o p t ) = η ( i = 1 n w i | C π ( i ) d π ( i ) | + w 0 q o p t ) + ( 1 η ) C max = i = 1 n λ i p π ( i ) A = a π ( 1 ) 1 b π ( 1 ) ( λ 1 + α λ 2 + α ( 1 + α ) λ 3 + + α ( 1 + α ) n 2 λ n ) + a π ( 2 ) 2 b π ( 2 ) ( λ 2 + α λ 3 + α ( 1 + α ) λ 4 + + α ( 1 + α ) n 3 λ n ) + + a π ( n ) n b π ( n ) λ n (3)

X i r = { 1 , J i r 0 , ,其中

V 1 = λ 1 + α λ 2 + α ( 1 + α ) λ 3 + + α ( 1 + α ) n 2 λ n V 2 = λ 2 + α λ 3 + α ( 1 + α ) λ 4 + + α ( 1 + α ) n 3 λ n V n 1 = λ n 1 + α λ n V n = λ n (4)

则问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max 可以转化为如下指派问题:

min i = 1 n r = 1 n C i r X i r (5)

s.t.

i = 1 n X i r = 1 , r = 1 , 2 , , n (6)

r = 1 n X i r = 1 , i = 1 , 2 , , n (7)

X i r = 0 1 , i , r = 1 , 2 , , n (8)

问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max 的具体求解算法如下:

算法1

步骤1:根据引理1计算出中位数l;

步骤2:根据(3),(4)计算出 C i r

步骤3:求解指派问题(5)~(8),确定工件的最优排序;

步骤4:由 q o p t = i = 1 l p π ( i ) A 得到共同松弛流。

定理1. 算法1可以解决问题 1 | S L K , q o p t , p i A = a i r b i + α t | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max ,且

算法的时间复杂度为 O ( n 3 )

证明 由引理1,2和上面的分析,可得算法的正确性。算法1中步骤1和步骤4的时间复杂度分别为 O ( n ) ,步骤2的时间复杂度为 O ( n 2 ) ,步骤3指派问题的时间复杂度为 O ( n 3 ) ,因此算法1总的时间复杂度为 O ( n 3 )

显然,当 b i = b , i = 1 , 2 , , n 时,我们有

Z ( π , q o p t ) = η ( i = 1 n w i | C π ( i ) d π ( i ) | + w 0 q o p t ) + ( 1 η ) C max = i = 1 n V i i b a π ( i ) (9)

由HLP规则(Hardy等 [14] ),式子 i = 1 n V i i b a π ( i ) 可按照最小的 V i i b 与最大的 a i 匹配,第二小的 V i i b 与第二

大的 a i 匹配,依次进行下去,直到结束,从而求得最优排序,该算法的时间复杂度为 O ( n log n ) 。因此,我们得到如下结论:

定理2. 问题 1 | S L K , q o p t , p i A = a i r b i + α t , b i = b | η ( i = 1 n ω i | C π ( i ) d π ( i ) | + ω 0 q o p t ) + ( 1 η ) C max 可以在

O ( n log n ) 时间内解决。

4. 结论

本文研究了在SLK工期指派下的单机排序问题,其中工件同时具有学习与恶化效应。目标是确定最优排序及共同松弛流使一个非正则目标函数(包括提前时间、延迟时间和共同松弛流的加权和,其中这里的权重为位置权重)和最大完工时间的线性组合最小。我们证明了这个问题在引入学习与恶化效应后仍然具有多项式时间算法。在以后的研究中,可以考虑这种模型在多机(包括流水作业和平行机)情况下如何求解。

基金项目

沈阳航空航天大学大学生创新创业训练计划项目(201810143273)。

文章引用

奚 汛,孙晓娜,王 崇,徐 卉,潘红霖,王吉波. 基于学习与恶化效应的松弛工期指派排序问题
Slack Due Date Assignment Scheduling Problem Based on Learning and Deterioration Effect[J]. 运筹与模糊学, 2020, 10(01): 30-35. https://doi.org/10.12677/ORF.2020.101003

参考文献

  1. 1. Biskup, D. (2008) A State-of-the-Art Review on Scheduling with Learning Effects. European Journal of Operational Research, 188, 315-329. https://doi.org/10.1016/j.ejor.2007.05.040

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

  3. 3. 王雪茹, 白雪莲, 王吉波, 殷娜. 基于截断学习效应的加权总完工时间流水作业排序问题研究[J]. 重庆师范大学学报, 2017, 34(5): 12-17.

  4. 4. Gawiejnowicz, S. (2008) Time-Dependent Scheduling. Springer, Berlin.

  5. 5. 王吉波, 郭苗苗, 刘桓, 李琳, 王丹. 具有依赖开工时间恶化工件的流水作业排序问题研究综述[J]. 沈阳航空航天大学学报, 2016, 33(3): 1-10.

  6. 6. 王吉波, 赵伯来. 具有独立调整时间和恶化效应的单机成组排序问题研究[J]. 沈阳航空航天大学学报, 2017, 34(4): 82-87.

  7. 7. Lee, W.C. (2004) A Note on Deteriorating Jobs and Learning in Single-Machine Scheduling Problems. International Journal of Business and Economics, 3, 83-89.

  8. 8. Wang, J.-B. (2006) A Note on Scheduling Problems with Learning Effect and Deteriorating Jobs. International Journal of Systems Science, 37, 827-833. https://doi.org/10.1080/00207720600879260

  9. 9. Yang, D.L. and Kuo, W.H. (2010) Some Scheduling Problems with Deteriorating Jobs and Learning Effects. Computer & Industrial Engineering, 58, 25-28. https://doi.org/10.1016/j.cie.2009.06.016

  10. 10. 王吉波, 梁茜茜, 张博. 带有学习与恶化效应的共同工期指派问题[J]. 重庆师范大学学报, 2019, 36(3): 1-6.

  11. 11. Liu, W., Hu, X. and Wang, X.-Y. (2017) Single Machine Scheduling with Slack Due Dates Assignment. Engineering Optimization, 49, 709-717. https://doi.org/10.1080/0305215x.2016.1197611

  12. 12. 王吉波, 牛玉萍, 刘璐, 郭倩. 同时具有学习和恶化效应的不同工期指派问题研究[J]. 沈阳师范大学学报, 2014, 32(3): 358-363.

  13. 13. Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326.

  14. 14. Hardy, G.H., Littlewood, J.E. and Polya, G. (1934) Inequalities. Cambridge University Press, Cambridge.

  15. NOTES

    *通讯作者。

期刊菜单