可控准备时间和加工时间的系列分批排序

罗成新, 张 雪

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



可控准备时间和加工时间的系列分批排序

罗成新, 张 雪

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

在许多实际生产环境中,工件的加工时间不是固定不变的,由于工人或机器的工作时间较长,其加工工件的效率降低,使得实际的加工时间加长,也就产生了所谓的退化效应。为考察退化效应对工件排序的影响,讨论在退化效应的条件下,研究工件带有可控准备时间和可控加工时间的单机系列批排序问题。在退化效应的条件下,工件的加工时间为它的开始时间的递增函数;所有的工件从一开始就被划分为连续的批次,并在单机上分批进行加工;在每批工件加工前,都有一个依赖于开始时间的准备时间。目标是确定工件的排序,并将其划分成批,从而最小化最大完工时间和最大延误,并且给出最优算法来求解最小化最大完工时间和最大延误问题。

系列分批; 排序; 退化效应; 单机; 准备时间; 可控

0 引 言

在传统的排序问题中,工件的加工时间为固定和独立的常数值。然而,在许多生产环境中经常会遇到工件的加工时间随时间变化的情况。自从Gupta等[1]以及Browne等[2]提出具有退化效应的排序问题以来,不断出现关于附加的研究各种具有退化效应的排序问题。批量生产,作为一种重要的加工方式,存在于许多排序环境中。批次的类型包括平行批和系列批。近年来,具有退化效应的平行分批排序问题已在一些文献中进行了研究,其中包括Qi等[3],Li等[4]和Miao等[5-6]。

一个类似本文研究的排序问题是具有退化效应的成组排序问题,其特点是成组技术的假设。在同样的生产要求下,工件提前分组。最近的研究已考虑具有退化效应的成组排序,包括Wu[7],Wang等[8-9],Zhang等[10],Yang[11]以及Bai[12]等。

有关本文的系列批加工的排序问题,关键地方有下面3处:

1) 在系列分批排序问题中,一个批内任意一个工件的完成时间等于该批的最后完工时间,即等于该批中最后一个工件的完工时间;

2) 系列分批加工问题考虑机器容量;

3) 系列分批排序问题,考虑工件分批和批顺序2个方面。

本文在Pei等[13]研究的基础上进行拓展,研究带有退化准备时间和退化加工时间的单机系列批排序问题,给出最优算法来求解最小化最大完工时间和最大延误问题。

1 问题描述

2 主要结论

(1)

其中n0=0。

证明 用归纳法来证明引理。当m=1时,

所以当m=1时,等式(1)成立。

假设当m=l时,等式(1)也成立,即

当m=l+1时,

所以当m=l+1时结论也正确。综上,引理1成立。

证明 由引理1得到引理2。

证明 假定π*是最优排序,π是另一个排序,π*和π的区别在于2个工件Ju和Jv互换,即π*=(W1,Bp,Bq,W2),π=(W1,(Bp{Ju})∪{Jv},(Bq{Jv})∪{Ju},W2),这里W1和W2表示部分排序。对于π*而言,Bq的完工时间是

在π中Bp,Bq的完工时间分别是

经整理后得

假设au

证明 假定在最优排序π*中存在批Bp(1≤p

其中

所以

又因为

所以有

显然Cmax(π)

基于上述分析,给出如下算法:

算法

第1步 把工件按照退化率ai非增的顺序排列,使得a1≥a2≥…≥an,得到工件列表。

第2步 在工件列表中,如果工件数大于u,就把前u个工件放在一个批中,然后以此规律迭代。否则,将剩余的工件放在一批。

第3步 在t0时刻按照他们生成的顺序按照批次进行加工。

证明 基于引理2,3,4,算法能够产生最优解。另外,最佳完工时间的结果可以按照(1)式得到。此外,算法的时间复杂度是O(nlogn)。证毕。

证明 因为有

3 结 语

本文研究了具有退化准备时间和退化加工时间的单机系列批排序问题。工件的加工时间是一个线性函数,并且每批工件被加工之前,都有一个依赖于开始时间的准备时间。目标是确定工件的排序,并将其划分成批,从而最小化最大完工时间。最后本文给出一个最优算法求解最小化最大完工时间问题和最大延误问题。

[ 1 ]GUPTAJND,GUPTASK.Singlefacilityschedulingwithnonlinearprocessingtimes[J].ComputIndEng, 1988,14(4):387-393.

[ 2 ]BROWNE S, YECHIALI U. Scheduling deteriorating jobs on a single processor[J]. Oper Res, 1990,38(3):495-498.

[ 3 ]QI Xianglai, ZHOU Shiguo, YUAN Jinjiang. Single machine parallel-batch scheduling with deteriorating jobs[J]. Theor Comput Sci, 2009,410(8):830-836.

[ 4 ]LI Shisheng, NG C T, YUAN Jingjiang, et al. Parallelbatch scheduling of deteriorating jobs with release dates to minimize the makespan[J]. Eur J Oper Res, 2011,210(3):482-488.

[ 5 ]MIAO Cuixia, ZHANG Yuzhong, CAO Zhigang. Bounded parallelbatch scheduling on single and multimachines for deteriorating jobs[J]. Inf Process Lett, 2011,111(16):798-803.

[ 6 ]MIAO Cuixia, ZHANG Yuzhong, WU Cuilian. Scheduling of deteriorating jobs with release dates to minimize the maximum lateness[J]. Theor Comput Sci, 2012,462:80-87.

[ 7 ]WU C C, LEE W C. Singlemachine group-scheduling problems with deteriorating setup times and job processing times[J]. Int J Prod Econ, 2008,115(1):128-133.

[ 8 ]WANG Jibo, LIN Lin, SHAN Feng. Singlemachine group scheduling problems with deteriorating jobs[J]. Int J Adv Manuf Technol, 2008,39(7):808-812.

[ 9 ]WANG Jibo, GAO Wenjun, WANG Liyan, et al. Single machine group scheduling with general linear deterioration to minimize the makespan[J]. Int J Adv Manuf Technol, 2009,43(1):146-150.

[10]ZHANG Xingong, YAN Guangle. Singlemachine group scheduling problems with deteriorated and learning effect[J]. Appl Math Comput, 2010,216(4):1259-1266.

[11]YANG S H. Group scheduling problems with simultaneous considerations of learning and deterioration effects on a singlemachine[J]. Appl Math Model, 2011,35(8):4008-4016.

[12]BAI Jing, LI Zhirong, HUANG Xue. Singlemachine group scheduling with general deterioration and learning effects[J]. Appl Math Model, 2012,36(3):1267-1274.

[13]PEI Jun, LIU Xinbao, FAN Wenjuan, et al. Single machine serial-batching scheduling with independent setup time and deteriorating job processing times[J]. Optim Lett, 2015,9(1):91-104.

[14]XUAN Hua, TANG Lixin. Scheduling a hybrid flowshop with batch production at the last stage[J]. Comput Oper Res, 2007,34(9):2718-2733.

Single machine serial-batching scheduling with controllable setup time and job processing times

LUOChengxin,ZHANGXue

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

In the actual production environment, we often encounter the situation that the job processing times vary with time. Because operator and machine work for a long time, the machine efficiency is lower, so the actual processing time becomes longer, which produces deterioration effects. In this paper, we study the single machine serial-batching scheduling problem, where both setup and job processing times are controllable by deteriorating effect. With the assumption of deteriorating jobs, the job processing times are described by an increasing function of their starting times. All the jobs are first partitioned into serial batches and then processed on a single serial-batching machine. Before each batch is processed, deteriorating setup time is required. The objective is to determine the optimal sequence of jobs, and partition the jobs in batches to minimize the makespan and the maximum lateness. We present an optimal algorithm to solve the problem of minimizing the makespan and the maximum lateness.

serial-batching; scheduling; deteriorating jobs; single machine; setup time; controllable

2015-04-27。

国家自然科学基金资助项目(11171050)。

罗成新(1958-),男,辽宁新宾人,沈阳师范大学教授,博士。

1673-5862(2016)02-0160-05

O223

A

10.3969/ j.issn.1673-5862.2016.02.007