李士生, 陳仁霞, 馮　琪, 孟金濤

(1.中原工學(xué)院, 鄭州450007; 2.鄭州航空工業(yè)管理學(xué)院, 鄭州 450015)

具有多重公共工期的單機(jī)退化工件排序

李士生1, 陳仁霞1, 馮琪1, 孟金濤2

(1.中原工學(xué)院, 鄭州450007; 2.鄭州航空工業(yè)管理學(xué)院, 鄭州 450015)

摘要：研究了需要同時(shí)確定最優(yōu)工件工期和加工序列的單機(jī)排序問(wèn)題。工件的加工時(shí)間是其開(kāi)工時(shí)間的線性增長(zhǎng)函數(shù)。每個(gè)工件的懲罰費(fèi)用包含兩部分，一部分是分配給它的工期費(fèi)用，另一部分是由機(jī)器上產(chǎn)生的提前及延遲懲罰費(fèi)用。管理者的目標(biāo)為最小化所有工件的總懲罰費(fèi)用。對(duì)于公共工期個(gè)數(shù)固定的情形，給出了一個(gè)多項(xiàng)式時(shí)間算法。

關(guān)鍵詞：?jiǎn)螜C(jī)排序；退化工件；多重公共工期

在主流的理論排序和應(yīng)用排序中，一個(gè)廣泛采用的假定是工件加工時(shí)間恒定不變。然而，在火災(zāi)搶險(xiǎn)、鋼鐵生產(chǎn)、金融管理、國(guó)防工業(yè)、緊急病房以及資源分配等許多工業(yè)工程中，任務(wù)(工件)的開(kāi)工時(shí)間越晚，其相應(yīng)的加工時(shí)間就越長(zhǎng)，需要花費(fèi)更多的時(shí)間和費(fèi)用來(lái)完成。這類工件的加工時(shí)間依賴其開(kāi)工時(shí)間的排序問(wèn)題在最近的十多年里得到了廣泛的關(guān)注[1-3]。

本文考慮需要確定工期分配的單機(jī)退化工件排序問(wèn)題。其中，給定一些需要在一臺(tái)機(jī)器上加工的工件，它們都在0時(shí)刻同時(shí)到達(dá)。每個(gè)工件有一個(gè)基本的加工時(shí)間，而實(shí)際加工時(shí)間是其開(kāi)工時(shí)間的一個(gè)線性增長(zhǎng)函數(shù)。相應(yīng)地，每個(gè)工件的懲罰費(fèi)用包含一個(gè)與分配給它的工期相關(guān)的費(fèi)用和排序所產(chǎn)生的提前及延遲費(fèi)用。管理者的目標(biāo)是所有工件的總懲罰費(fèi)用達(dá)到最小。本文假定需要分配的公共工期的個(gè)數(shù)是預(yù)先確定的。

這類需要同時(shí)確定最優(yōu)工期分配和工件序列的排序問(wèn)題在工程管理中已經(jīng)廣泛應(yīng)用，吸引了大量學(xué)者的研究興趣。對(duì)工期分配研究的動(dòng)機(jī)在于訂單的交貨期通常并不是由生產(chǎn)商或者商家單方面確定的，而是由這兩者通過(guò)協(xié)商滿足各自的要求而決定的。由于交貨期定的時(shí)間太短，生產(chǎn)商難以按時(shí)完成而需承擔(dān)相應(yīng)的違約責(zé)任及信譽(yù)損失，而如果交貨期定的時(shí)間太長(zhǎng)，商家又可能錯(cuò)過(guò)銷售旺季遭受損失，因而確定一個(gè)達(dá)到雙方平衡或者折衷的交貨期就很重要[4-5]。

1問(wèn)題描述

本文給定一個(gè)包含一臺(tái)處理工件的機(jī)器和n個(gè)等待加工的工件(J1,J2,…,Jn)的系統(tǒng)。這n個(gè)工件在0時(shí)刻同時(shí)到達(dá)。工件的加工時(shí)間是其開(kāi)工時(shí)間的線性增長(zhǎng)函數(shù)。工件Jj是由一個(gè)基本的加工時(shí)間aj刻畫的。如果工件Jj在時(shí)刻tj開(kāi)始加工，則它的實(shí)際加工時(shí)間pj可表示為pj=aj+btj,j=1,2,…,n,其中b(b>0)是與工件無(wú)關(guān)的退化率。需要分配的不同公共工期數(shù)m是預(yù)先確定且已知的。對(duì)于一個(gè)給定的排序σ，用Cj=Cj(σ)表示工件Jj的完工時(shí)間。令dj表示工件Jj的工期，Ej=max{0,dj-Cj}表示工件Jj的提前時(shí)間，Tj=max{0,Cj-dj}表示工件Jj的延遲時(shí)間。此外，用α、β和γ分別表示工期、提前和延遲的單位時(shí)間懲罰費(fèi)用。同時(shí)，本文用D1≤D2≤…≤Dm表示這m個(gè)不同的待定工期，Ni表示分配給工期Di的工件集，i=1,2,…,m。

管理者的目標(biāo)是確定最優(yōu)的D={D1,D2,…,Dm}、N={N1,N2,…,Nm} 以及排序σ，使得總懲罰費(fèi)用函數(shù)F(D,N,σ)達(dá)到最小，其中

(1)

這里dj=Di對(duì)所有Jj∈Ni都成立。

如果α≥γ,容易證明上面的問(wèn)題等價(jià)于總完工時(shí)間之和達(dá)到最小的排序問(wèn)題，則對(duì)所有的j=1,2,…,n，置dj=0,且工件按照最短的基本加工時(shí)間優(yōu)先加工的準(zhǔn)則是最優(yōu)的。因此，在下面的論述中假定α<γ。

2|Ni|=ni已知的情形

當(dāng)工期D和排序σ給定時(shí)，下面的引理給出一個(gè)最優(yōu)N的劃分。它意味著存在一個(gè)最優(yōu)排序，使得處于位置Δi-1+1與Δi之間的ni個(gè)相繼工件都分配給Ni。

引理1對(duì)于給定的D和σ, 存在著一個(gè)最優(yōu)的N滿足Ni={J[Δi-1+1],J[Δi-1+2],…，J[Δi]},i=1,2,…,m,其中J[r]是σ中處于第r個(gè)位置的工件。

證明：只需找到N的一個(gè)最優(yōu)劃分，使得σ中處于前n1個(gè)位置的工件分配給N1,接下來(lái)n2個(gè)位置的工件分配給N2,以此類推。通過(guò)工件交換的策略及基本的數(shù)學(xué)推導(dǎo)，可以得到所需的性質(zhì)。

類似于文獻(xiàn)[6-7]中關(guān)于單個(gè)公共工期的情形, 下面的兩個(gè)引理成立。

引理2對(duì)于給定的D和σ，存在一個(gè)最優(yōu)的排序，使得Ni(i=1,2,…,m)中的工件在機(jī)器上連續(xù)加工而沒(méi)有空閑時(shí)間。

引理3對(duì)于給定的σ,存在一個(gè)最優(yōu)的D，使得每一個(gè)Di剛好與Ni中某一個(gè)工件的完工時(shí)間重合，i=1,2,…,m。

引理4對(duì)于給定的σ,存在一個(gè)最優(yōu)排序，使得機(jī)器在0時(shí)刻開(kāi)工且相繼工件之間不存在空閑時(shí)間。

證明：由于工件開(kāi)工越晚，其加工時(shí)間就越長(zhǎng)，結(jié)合引理1和引理3，運(yùn)用工件遷移的策略可以得到所需的性質(zhì)。

結(jié)合引理1及引理4的結(jié)論，存在一個(gè)最優(yōu)排序，使得機(jī)器上沒(méi)有任何空閑時(shí)間，因而為了尋找最優(yōu)解，只需考慮工件序列即可。

引理5對(duì)于給定的σ, 存在一個(gè)最優(yōu)排序，使得Di=C[hi],其中

(2)

基于引理5,類似于Chand S和Chhajed D的分析及討論[8]，有下面的結(jié)論。

引理6排序中處于第j個(gè)位置的工件位置權(quán)重可以表示如下：

(3)

因此，公式(1)可以重新表述如下：

(4)

對(duì)任意給定的工件加工序列σ=J[1]→J[2]→…→J[n],工件的實(shí)際加工時(shí)間可以計(jì)算如下：

(5)

因此，將公式(5)代入公式(4),則公式(2)可以進(jìn)一步重新表述如下：

(6)

其中:

(7)

算法1:

步驟2：對(duì)i=1,2,…,m,利用公式(2)計(jì)算hi的值。

定理1對(duì)給定的m, 當(dāng)|Ni|=ni已知時(shí)，最優(yōu)化問(wèn)題可以在O(nlogn)時(shí)間內(nèi)由算法1解決。

證明： 算法的正確性是由引理1至引理6以及上面的討論所保證的。對(duì)于算法的時(shí)間界，步驟1和步驟2可以在O(m)時(shí)間內(nèi)完成，步驟3可以在O(n)時(shí)間內(nèi)完成，步驟4可以在O(nlogn)時(shí)間內(nèi)完成，步驟5可以在O(n)時(shí)間內(nèi)完成。由于m≤n，因此算法1可以在O(nlogn)時(shí)間內(nèi)完成。

算例給定n=10個(gè)工件，其基本加工時(shí)間見(jiàn)表1, 工期、提前和延誤的單位時(shí)間懲罰費(fèi)用分別為α=2,β=11,γ=18。所有工件具有m=2個(gè)分配的工期，其中n1=4,n2=6。工件的退化率b=0.1。

表1　工件的基本加工時(shí)間

按照算法1前三步執(zhí)行，可以得到Δ1=4,Δ2=10,h1=3,p=8。相應(yīng)地，這10個(gè)工件的位置權(quán)重及相應(yīng)的指標(biāo)計(jì)算見(jiàn)表2。

表2　退化率b=0.1時(shí)的位置權(quán)重及相應(yīng)指標(biāo)

利用表2中的結(jié)果，最優(yōu)的工件加工序列為:

J3→J2→J1→J4→J8→J7→J6→J9→J5→J10

3|Ni|=ni未知的情形

假定向量(n1,n2,…,nm)也是需要確定的,D、N和σ都是判定變量。下面的引理表明可以將搜索限制到n1≥n2≥…≥nm的情形。

利用引理7的結(jié)果，給出這種情形下的最優(yōu)化算法如下。

算法2：

步驟2：利用算法1計(jì)算(n1,n2,…,nm)狀態(tài)時(shí)的最小懲罰費(fèi)用。

定理2對(duì)給定的m, 當(dāng)|Ni|=ni需要確定時(shí)，最優(yōu)化問(wèn)題可以在O(nmlogn)時(shí)間內(nèi)由算法2解決。

4結(jié)語(yǔ)

本文研究了一類需要同時(shí)確定最優(yōu)工件和工期加工序列的退化工件排序問(wèn)題。工件的加工時(shí)間是其開(kāi)工時(shí)間的線性增長(zhǎng)函數(shù), 管理者需要對(duì)這些工件設(shè)定m個(gè)工期。與以往文獻(xiàn)中通常考慮單個(gè)公共工期不同, 這里我們考慮多重公共工期的情形，給出了一個(gè)多項(xiàng)式時(shí)間最優(yōu)算法。下一步的研究工作可以考慮多臺(tái)平行機(jī)的情形以及工件加工時(shí)間是其開(kāi)工時(shí)間的非線性增長(zhǎng)函數(shù)的情形。

參考文獻(xiàn)：

[1]Alidaee B, Womer N K. Scheduling with Time Dependent Processing Times: Review and Extensions [J]. Journal of the Operational Research Society, 1999, 50: 711-720.

[2]Cheng T C E, Ding Q, Lin B M T. A Concise Survey of Scheduling with Time-dependent Processing Times [J]. European Journal of Operational Research, 2004, 152: 1-13.

[3]Gawiejnowicz S. Time-dependent Scheduling [M]. Berlin: Springer-Verlag, 2008.

[4]Gordon V S, Proth J M, Strusevich V A. Scheduling with Due Date Assignment, in Leung J Y T (Ed.), Handbook of Scheduling [M]. Boca Raton : CRC Press, 2004.

[5]Gordon V S, Strusevich V A, Dolgui A. Scheduling with Due Date Assignment Under Special Conditions on Job Processing [J]. Journal of Scheduling, 2012, 15: 447-456.

[6]Brucker P. Scheduling Algorithms (Fifth edition) [M]. Berlin: Springer-Verlag, 2007.

[7]Panwalkar S S, Smith M L, Seidmann A. Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem [J]. Operations Research, 1982, 30: 391-399.

[8]Chand S, Chhajed D. A Single Machine Model for Determination of Optimal Due Dates and Sequence [J]. Operations Research, 1992, 40: 596-602.

[9]Hardy G H, Littlewood J E, Polya G. Inequalities [M]. London: Cambridge University Press, 1967.

(責(zé)任編輯：王長(zhǎng)通)

Multiple Common Due Dates Scheduling with

Deteriorating Jobs on a Single Machine

LI Shi-sheng1, CHEN Ren-xia1, FENG Qi1, MENG Jin-tao2

(1.Zhongyuan University of Technology, Zhengzhou 450007,

2.Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015, China)

Abstract:This paper considers the problem of simultaneous determination of optimal due dates and optimal sequence on a single machine. The actual processing time of a job is a linear increasing function of its starting time. The penalty for a job is assumed to be a linear function of the due date and the earliness/tardiness for the job. The objective function is to minimize the total penalty for all jobs. An efficient polynomial-time algorithm is presented to solve the problem with a given number of multiple common due dates.

Key words:single-machine scheduling; deteriorating jobs; multiple common due dates

文章編號(hào)：1671-6906(2015)01-0063-04 1671-6906(2015)01-0005-04

作者簡(jiǎn)介：張文勇(1961-)，男，河南鄭州人，教授。 楊蕾(1979-)，女(回族)，河南洛陽(yáng)人，副教授，博士，研究方向?yàn)榱Ⅲw圖像處理、多媒體通信等。

基金項(xiàng)目：河南省科技攻關(guān)項(xiàng)目(142102210523)；鄭州市重點(diǎn)科技攻關(guān)項(xiàng)目(201306023) 國(guó)家自然科學(xué)基金項(xiàng)目(60902063，61440031)；河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目 (092300410175)；河南省科技創(chuàng)新人才計(jì)劃科技創(chuàng)新杰出青年資助項(xiàng)目(124100510015)

收稿日期：2014-10-30 2014-04-03

中圖分類號(hào)：O223

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1671-6906.2015.01.001