Advances in Applied Mathematics
Vol. 09  No. 03 ( 2020 ), Article ID: 34542 , 5 pages
10.12677/AAM.2020.93040

Research on Common Due Date Assignment Scheduling Problem with Truncated Learning Effect

Changlin Zhao, Tao Wu, Yuhao Ma, Liqiang Zhang, Jianqiang Wu, Jibo Wang*

School of Science, Shenyang Aerospace University, Shenyang Liaoning

Received: Feb. 25th, 2020; accepted: Mar. 9th, 2020; published: Mar. 16th, 2020

ABSTRACT

This paper studies a single machine scheduling problem with truncated learning effect, where the actual processing time of a job depends on the position and truncation factor. Under the slack due date assignment, the objective is to determine the schedule of jobs and the common due date in order to minimize the linear weighted sum of the earliness, tardiness, common due date and total completion time, where the weights of the earliness and tardiness are positional weights. We prove that the problem can be solved in polynomial time.

Keywords:Scheduling, Learning Effect, Common Due Date Assignment

基于截断学习效应的共同工期指派调度 问题研究

赵常霖,吴涛,马宇豪,张立强,武建强,王吉波*

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

收稿日期:2020年2月25日;录用日期:2020年3月9日;发布日期:2020年3月16日

摘 要

研究工件加工时间具有截断学习效应的单机调度问题,其中工件的加工时间与所排位置和截断因子都有关系。在共同工期指派下,目标是确定工件的加工顺序和共同工期使得工件的提前时间、延误时间、工期和总完工时间的线性加权和最小,其中提前时间和延误时间的权重为位置权重。证明了此问题是多项式时间可解的。

关键词 :调度,学习效应,共同工期指派

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

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

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

1. 引言

随着信息化时代的到来,全球制造业、供应链物流及服务业迅速发展,很多企业面临着一个共同的问题,即如何统筹安排各部门的生产使得在现有的生产条件下获得最大的产出,调度(也称排序)理论应运而生。在实际的生产过程中,学习效应产生的背景是工件的加工时间会随着机器(比如技术工人)熟练度的提升等因素而使后来加工的工件实际加工时间变短(参加综述文献Biskup [1],Azzouz等 [2]),但工件的加工时间不能无限的缩短,它要有一个限制,即截断学习效应。Cheng等 [3] 考虑了工件具有截断学习效应的流水作业调度问题,在两台机器环境下,他们对最大完工时间极小化问题进行了研究,给出了求解算法。王雪茹等 [4] 研究了工件具有截断学习效应的流水作业调度问题,在两台机器环境下,他们对加权总完工时间极小化问题进行了研究,此问题是NP-难的,他们给出了分支定界算法和启发式算法来求解此问题。Wang等 [5] 研究了每个工件的学习效应都不一样的截断学习效应单机调度问题,对一些正则和非正则目标函数,他们给出了一些结论。Wang等 [6] 考虑了工件具有对数截断学习效应的流水作业调度问题,在多台机器环境下,他们对最大完工时间和加权总完工时间极小化问题分别进行了研究,给出了求解算法(包括分支定界算法和启发式算法)。

上面讨论的截断学习效应问题,大多数是研究正则目标函数,即工件的费用是完工时间的非减函数,本文将讨论非正则目标函数,即在共同工期(CON)指派下,工件加工时间具有截断学习效应的单机调度问题,目标是确定工件的加工顺序和共同工期使得工件的提前时间、延误时间、工期和总完工时间的线性加权和最小,其中提前时间和延误时间的权重为位置权重,并证明这个问题都是多项式时间可解的。

2. 问题描述

有n个工件 J = { J 1 , J 2 , , J n } ,零时刻到达,要在一台机器上加工,且加工过程中工件不允许中断。Wang等 [5] 假设工件 J i 排在第h个位置的实际加工时间为 p i h = p ¯ i max { h a i , b } i , h = 1 , 2 , , n ,我们考虑更一般的情况,即假设工件 J i 排在第h个位置的实际加工时间为

p i h = p ¯ i max { h a i , b i } , i , h = 1 , 2 , , n , (1)

其中 p ¯ i 为工件 J i 的基本加工时间, a i 0 为工件 J i 的学习因子, 0 < b i 1 为工件 J i 的截断因子。令工件 J i 的完工时间为 C i ,所有工件有一个共同(CON)的工期d。如果工件 J i 的完工时间在工期d之前(之后),则受到提前(延误)惩罚,目标是确定一个工件序列 π = [ J π ( 1 ) , J π ( 2 ) , , J π ( n ) ] 和d使目标函数

F ( π , d ) = i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) (2)

最小,其中 π ( i ) 表示在排序中的第i个位置, w i 为第i个位置的权重(即位置权重), w 0 为d的权重, w n + 1 为总完工时间 i = 1 n C π ( i ) 的权重。用Graham等 [7] 的三参数表示法,此问题可表示为

1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) , (3)

其中,CON表示共同工期指派,TLE表示截断学习效应(1)。

在工件加工时间为常数的情况下,Brucker [8] 研究了问题 1 | | i = 1 n w i | C π ( i ) d | + w 0 d ,他证明了这个问题是多项式时间可解的。下面我们研究更一般的截断学习效应调度问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i )

3. 主要结论

引理1:存在一个最优工件序列,从第一个工件开始加工到最后一个工件结束,机器加工无空闲,且第一个工件在零时刻开始加工。

证明:与Brucker [8] 的证明方法类似,如果机器在加工工件的过程中存在空闲时间,则可以通过减少空闲时间到0,而使目标函数 F ( π , d ) = i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 不增加,得证。

引理2:对于给定的序列 π = [ J π ( 1 ) , J π ( 2 ) , , J π ( n ) ] ,最优的决策变量d等于某个工件的完工时间,即 d = C π ( k ) ,其中k是使不等式 j = 0 k 1 w j j = k n w j j = 0 k w j j = k + 1 n w j 成立的某个整数。

证明:与Brucker [8] 的证明方法类似。假设 C π ( k ) < d < C π ( k + 1 ) ,则可通过调整d,使其等于某个工件的完工时间,从而使目标函数 F ( π , d ) = i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 不增加,得到矛盾。

引理3:问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 的目标函数可以写为 F ( π , d ) = i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) = i = 1 n ϑ i p π ( i ) A ,其中 p π ( i ) A 为排在第i个位置的实际加工时间,

ϑ i = { w 0 + l = 1 i 1 w l + ( n i + 1 ) w n + 1 , i = 1 , 2 , , k l = i n w l + ( n i + 1 ) w n + 1 , i = k + 1 , k + 2 , , n (4)

证明:假设给定最优工件序列为 π = [ J π ( 1 ) , J π ( 2 ) , , J π ( n ) ] d = C π ( k ) ,可知

F ( π , d ) = i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) = i = 1 k 1 w i ( C π ( k ) C π ( i ) ) + i = k + 1 n w i ( C π ( i ) C π ( k ) ) + w 0 C π ( k ) + w n + 1 i = 1 n C π ( i ) = i = 1 k 1 w i ( l = i + 1 k p π ( l ) A ) + i = k + 1 n w i ( l = k + 1 i p π ( l ) A ) + w 0 l = 1 k p π ( l ) A + w n + 1 i = 1 n ( n i + 1 ) p π ( i ) A = i = 1 n ϑ i p π ( i ) A

其中 ϑ i = { w 0 + l = 1 i 1 w l + ( n i + 1 ) w n + 1 , i = 1 , 2 , , k l = i n w l + ( n i + 1 ) w n + 1 , i = k + 1 , k + 2 , , n

由引理3可知

F ( π , d ) = i = 1 n ϑ i p π ( i ) A = i = 1 n ϑ i p ¯ π ( i ) max { i a π ( i ) , b π ( i ) } (5)

显然(5)式的极小化问题可以转化为指派问题。令

C i h = ϑ h p ¯ i max { h a i , b i } (6)

x i h = { 1 , J i h , 0 , , (7)

则调度问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 的最优调度可以用如下的指派问题得到。

min i = 1 n h = 1 n C i h x i h (8)

s.t.

h = 1 n x i h = 1 , i = 1 , 2 , , n (9)

i = 1 n x i h = 1 , h = 1 , 2 , , n (10)

x i h = 0 1 , i , h = 1 , 2 , , n (11)

由以上分析,可以给出问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 的解决算法。

算法1:

步骤1:根据引理2计算出k的值;

步骤2:根据(6)计算出 C i h

步骤3:求解指派问题(8)~(11),得到工件的最优调度及最小的目标函数值;

步骤4:由 d = C π ( k ) 得到共同工期。

定理1:问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 可由算法1解决且算法的时间复杂度为 O ( n 3 )

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

下面考虑一特殊情况,解决该调度问题的时间复杂性会降低,即特殊情况: a i = a , b i = b , i = 1 , 2 , , n , ( a 0 , 0 < b 1 ) ,则目标函数为

F ( π , d ) = i = 1 n ϑ i p π ( i ) A = i = 1 n ϑ i p ¯ π ( i ) max { i a , b } (12)

β i = ϑ i max { i a , b } ,则 F ( π , d ) = i = 1 n ϑ i p π ( i ) A = i = 1 n β i p ¯ π ( i ) ,由Hardy等 [9] 得,式子 i = 1 n β i p ¯ π ( i ) 的最小值,能够通过两个序列 { β i } { p ¯ π ( i ) } 的相反序列匹配得到。

由(12)和上面分析,问题 1 | C O N , T L E | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 的特殊情况 a i = a , b i = b , i = 1 , 2 , , n ,可由下面的算法解决。

算法2:

步骤1:根据引理2计算出k的值;

步骤2:计算出 α i = ϑ i max { i a , b }

步骤3:按照最小的 β i 与最大的 p ¯ i 匹配,第二小的 β i 与第二大的 p ¯ i 匹配,依次进行下去,直到结束,从而求得工件的最优调度及最小的目标函数值;

步骤4:由 d = C π ( k ) 得到共同工期。

定理2:问题 1 | C O N , T L E , a i = a , b i = b | i = 1 n w i | C π ( i ) d | + w 0 d + w n + 1 i = 1 n C π ( i ) 可由算法2解决且算法的时间复杂度为为 O ( n log n )

证明:算法1中步骤1,2和步骤4的时间复杂度分别为 O ( n ) ,步骤3的时间复杂度为 O ( n log n ) ,因此算法2总的时间复杂度为 O ( n log n )

基金项目

沈阳航空航天大学大学生创新创业训练计划项目:201910143415。

文章引用

赵常霖,吴 涛,马宇豪,张立强,武建强,王吉波. 基于截断学习效应的共同工期指派调度问题研究
Research on Common Due Date Assignment Scheduling Problem with Truncated Learning Effect[J]. 应用数学进展, 2020, 09(03): 341-345. https://doi.org/10.12677/AAM.2020.93040

参考文献

  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. Azzouz, A., Ennigrou, M. and Said, L.B. (2018) Scheduling Problems under Learning Effects: Classification and Cartography. International Journal of Production Research, 56, 1642-1661. https://doi.org/10.1080/00207543.2017.1355576

  3. 3. Cheng, T.C.E., Wu, C.-C., Chen, J.-C., Wu, W.-H. and Cheng, S.-R. (2013) Two-Machine Flowshop Scheduling with a Truncated Learning Function to Minimize the Makespan. International Journal of Production Economics, 141, 79-86. https://doi.org/10.1016/j.ijpe.2012.03.027

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

  5. 5. Wang, X.-R., Jin, J., Wang, J.-B. and Ji, P. (2014) Single Machine Scheduling with Truncated Job-Dependent Learning Effect. Optimization Letters, 8, 669-677. https://doi.org/10.1007/s11590-012-0579-0

  6. 6. Wang, J.-B., Liu, F. and Wang, J.-J. (2019) Research on m-Machine Flow Shop Scheduling with Truncated Learning Effects. International Transactions in Operational Research, 26, 1135-1151. https://doi.org/10.1111/itor.12323

  7. 7. 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. https://doi.org/10.1016/S0167-5060(08)70356-X

  8. 8. Brucker, P. (2001) Scheduling Algorithms. 3rd Edition, Springer, Berlin. https://doi.org/10.1007/978-3-662-04550-3

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

期刊菜单