帶有交貨期窗口和加工時間可控的排序問題

趙傳立, 張 蕾

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

?

帶有交貨期窗口和加工時間可控的排序問題

趙傳立, 張 蕾

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

討論了帶有交貨期窗口和加工時間可控的單機排序問題。工件的加工時間是關于分配資源量的凸函數模型。工件若在交貨期窗口前完工,則產生提前費用;若在交貨期窗口后完工,則產生延誤費用。分別研究了多窗口問題和單窗口問題。目標是在關于提前、延誤、交貨期窗口開始時間、交貨期窗口大小和最大完工時間的函數約束條件下,確定工件的最優加工順序、最優加工時間、極小化資源費用函數。通過將2個問題分別轉化為指派問題,證明了2個問題是多項式時間可解的,問題的計算復雜性是O(n3)。

排序; 單機; 交貨期窗口; 加工時間可控; 多項式時間算法

0 引 言

在經典的排序模型中,每個工件有固定的加工時間,但在實際的生產過程中,工件的加工時間并不是不變的,可能會受到退化效應、學習效應、分配的資源量、工件的加工位置等因素的影響。近年來,關于加工時間可控的排序問題的研究越來越多。Liu等[1]研究了帶有交貨期窗口和加工時間是關于資源量的凸函數模型的單機排序問題,目標是在約束條件下極小化資源消耗費用之和,給出了多項式時間算法,計算復雜性為O(nlogn)。Yang等[2]討論了帶有多個交貨期窗口和加工時間可控的排序問題,針對多個目標函數分別給出了多項式時間算法。Yang等[3]對帶有維修活動和可控加工時間的平行機問題進行了研究,目標是極小化總完工時間,證明了該問題是多項式時間可解的。Rudek等[4]研究了帶有資源的流水作業的排序問題,目標是極小化最大完工時間,給出了多項式時間算法。Shabtay等[5]對于加工時間可控的若干排序問題做出了詳細綜述。

在帶有交貨期窗口的排序問題中,提前、延誤完工都會產生相應的懲罰。趙傳立等[6]考慮了帶有交貨期窗口和維修活動的單機排序問題。工件的加工時間為所在位置的非減函數模型,通過將問題分別轉換為指派問題,證明了該問題是多項式時間可解的。Mor等[7]提出了帶有維修活動和多窗口的單機排序問題,通過對不同類型的維修活動進行分析,給出了計算復雜性O(n4)的多項式時間算法。Wang等[8]提出了具有學習效應、資源和交貨期窗口的單機排序問題,并且證明了該問題是多項式時間可解的,給出了計算復雜性為O(n3)的多項式時間算法。Yin等[9]研究了每個工件都有自己的交貨期窗口和加工時間可控的單機排序問題,證明了該問題是多項式時間可解的。Wang等[10-11]討論了同時帶有學習效應、退化效應和交貨期窗口的排序問題,分別給出了多項式時間算法。Zhao等[12]研究了所有工件有一個共同的交貨期窗口,并且帶有退化效應和維修活動的單機排序問題,目標是極小化提前、延誤、交貨期窗口開始時間、交貨期窗口大小總費用函數,并且給出了多項式時間算法,證明了該問題是多項式時間可解的。

在文獻[1]的基礎上,對帶有交貨期窗口和加工時間是關于資源的凸函數模型的排序問題進行了研究,證明了該問題是多項式時間可解的。

1 問題描述

設有n個工件{J1,J2,…,Jn}在1臺機器上加工,所有工件零時刻到達,機器在同一時間只可加工1個工件,加工過程不可中斷?？紤]的加工時間模型如下:

其中:wj≥0是工件Jj的基本加工時間;r是工件Jj在排序中所處的位置;aj≤0(aj≥0)是工件Jj的學習率(退化率);uj>0是分配給工件Jj的資源量;k是正參數。

引用三參數表示法將本文所要研究的問題表示成

1) 每個工件的加工不可中斷,機器無空閑狀態,第1個工件在零時刻開始加工;

(1)

(2)

證明 給定的一個排序π=(J[1],J[2],…,J[n]),由拉格朗日乘子法,設

(3)

對于式子(3),分別對u[j],λ求偏導,可以得到

(4)

(5)

由式(4)得到

(6)

則

(7)

由式(5)和式(7)得到

(8)

則

(9)

將式(9)代入式(7),得到式(2)。

考慮到問題1是針對全部排序,求Z*的最小值可以通過指派問題進行求解,設

(10)

定義變量χij,如果工件i排在第j個位置上,則χij=1;否則,χij=0。

則問題1轉化為下列指派問題

算法1

步驟2 通過式(10)計算τij,i=1,…,n,j=1,…,n;

步驟4 通過解決指派問題Z*,確定工件的最優排序,記最優排序為π*=(J[1],J[2],…,J[n]);

證明 算法1中,步驟4的計算復雜性為O(n3),步驟1、2、3均可以在線性時間內解決。因此,算法1整體的計算復雜性為O(n3)。

1) 每個工件的加工不可中斷,機器無空閑狀態,第1個工件在零時刻開始加工;

(11)

(12)

證明同上一問題。

φj可通過式(11)計算得到,

同理,Z*可以通過指派問題進行求解,設

(13)

定義變量χij,如果工件i排在第j個位置上,則χij=1;否則,χij=0。

則問題2轉化為下列指派問題

算法2

步驟2 通過式(13)計算τij,i=1,…,n,j=1,…,n;

步驟3 通過式(12)計算出最優資源分配量u*[j],j=1,…,n;

步驟4 通過解決指派問題Z*,確定工件的最優排序,記最優排序為π*=(J[1],J[2],…,J[n]);

證明 算法2中,步驟4的計算復雜性為O(n3),步驟1、2、3均可以在線性時間內解決。因此,算法2整體的計算復雜性為O(n3)。

4 結 論

討論了帶有交貨期窗口和加工時間可控的單機排序問題。工件的加工時間受工件的基本加工時間、工件的加工位置、學習率(退化率)、分配的資源量影響。在關于提前、延誤、窗口開始時間、窗口大小、最大完工時間的總費用函數的約束條件下,極小化資源費用函數。通過對多窗口和單窗口問題的分別討論,將問題轉換成了相應的指派問題,構造了多項式時間算法,證明了所研究的問題是多項式時間可解的。進一步的研究可以考慮其他單機或平行機問題。

[1]LIU Lu,WANG Jianjun, WANG Xiaoyuan. Single machine due-window assignment scheduling with resource-dependent processing times to minimize total resource consumption cost[J]. Int J Prod Res, 2016,54(4):1186-1195.

[2]YANG D L, LAI C J, YANG S J. Scheduling problems with multiple due windows assignment and controllable processing times on a single machine[J]. Int J Prod Econ, 2014,150:96-103.

[3]YANG D L, CHENG T C E, YANG S J. Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimize total cost involving total completion time and job compressions[J]. Int J Prod Res, 2014,52(4):1133-1141.

[4]RUDEK A, RUDEK R. On flowshop scheduling problems with the aging effect and resource allocation[J].Int J Adv Manuf Technol, 2012,62(1):135-145.

[5]SHABTAY D, STEINER G.A survey of scheduling with controllable processing times[J]. Disc Appl Math, 2007,155(13):1643-1666.

[6]LI Weixuan, ZHAO Chuanli.Single machine due window assignment and scheduling with an optional maintenance activity[J]. Adv Mater Res, 2014,1006/1007:437-440.

[7]MOR B, MOSHEIOV G. Scheduling a deteriorating maintenance activity and due-window assignment[J]. Comput Oper Res, 2015,57:33-40.

[8]WANG Jibo, WANG Mingzheng. Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times[J]. Asia Pac J Oper Res, 2014,31(5):1450036.

[9]YIN Y Q, CHENG T C E, WU C C, 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):1-13.

[10]WANG Jibo, WANG Cheng. Single-machine due-window assignment problem with learning effect and deteriorating jobs[J]. Appl Math Model, 2011,35(8):4017-4022.

[11]WANG Jibo, LIU Lu, WANG Cheng. Singlemachine SLK/DIF duewindowassignment problem with learning effect and deteriorating jobs[J]. Appl Math Model, 2013,37:8394-8400.

[12]ZHAO Chuanli, TANG Hengyong. A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity[J]. Comput Oper Res, 2012,39(6):1300-1303.

[13]MOSHEIOV G,ORON D. Job-dependent due-window assignment based on a common flow allowance[J]. Found Comput Dec Sci, 2010,35(3):185-195.

[14]WU Yubin, WAN Long, WANG Xiaoyuan. Study on due-window assignment scheduling based on common flow allowance[J]. Int J Prod Econ, 2015,165:155-157.

[15]LIMAN S D, PANWALKAR S S, THONGMEE S. Common due window size and location determination in a single machine scheduling problem[J]. J Oper Res Soc, 1998,49(9):1007-1010.

Single machine due-window assignment and scheduling with controllable processing times

ZHAOChuanli,ZHANGLei

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

In this paper, we consider a kind of single-machine scheduling problem with due-window assignment and scheduling with controllable job processing times. The processing time of each job is the convex resource function. If the job is completed outside the due-window, it would be penalized according to its earliness or tardiness value. We consider two models. In the first model, each job has its own due-window.In the second model, all the jobs have the common due-window. The objective is to determine the optimal sequence, the optimal processing times and to minimize the total resource consumption cost under the constraint that the scheduling cost is related to earliness, tardiness, the starting time of due-window, the size of due-window and the makespan. By converting the two scheduling problems into assignment problems, we prove that the scheduling problems can both be solved in polynomial time and the complexities of the two problems are bothO(n3).

scheduling; single machine; controllable processing time; polynomial time

2016-07-08。

遼寧省教育廳科學研究一般項目(L2014433)。

趙傳立(1958-),男,黑龍江泰來人,沈陽師范大學教授,博士。

1673-5862(2016)04-0402-07

運籌學與控制論

O223

A

10.3969/ j.issn.1673-5862.2016.04.005