具有模糊交貨期并賦有延遲懲罰的平行機(jī)排序問(wèn)題

葉彩虹

(重慶師范大學(xué)數(shù)學(xué)學(xué)院,重慶 401331)

具有模糊交貨期并賦有延遲懲罰的平行機(jī)排序問(wèn)題

葉彩虹

(重慶師范大學(xué)數(shù)學(xué)學(xué)院,重慶 401331)

考慮具有模糊交貨期并賦有延遲懲罰的平行機(jī)排序問(wèn)題,討論了賦有延遲懲罰的排序問(wèn)題和總誤工問(wèn)題,模型中利用三角形模糊數(shù)把交貨期表示出來(lái),工件具有準(zhǔn)備時(shí)間,并且工件允許中斷,目標(biāo)是有一最優(yōu)序列能夠得到最大延誤懲罰,用滿意度來(lái)討論總誤工時(shí)間,并且得到最優(yōu)排序以便最小化總誤工時(shí)間,對(duì)這些問(wèn)題,給出算法.

排序;模糊交貨期;三角形模糊數(shù);準(zhǔn)備時(shí)間;滿意度

排序問(wèn)題是組合優(yōu)化中一個(gè)極為重要的課題,而往往在現(xiàn)實(shí)的加工過(guò)程中,由于有許多的不確定因素,很難事先確定工件的加工時(shí)間和工期,因此研究不確定環(huán)境下的生產(chǎn)調(diào)度問(wèn)題有著重要的意義.事實(shí)上,早在1979年,Prade[1]就將模糊集的理論用于生產(chǎn)調(diào)度問(wèn)題的研究;霍錄景和米洪海[2]利用三角形模糊數(shù)考慮了平行機(jī)具有模糊交貨期的最大延誤問(wèn)題,并給出算法和一些定理;袁芬和谷云東[3]等人討論了平行機(jī)具有模糊交貨期的一些性質(zhì)和一些比較好的結(jié)果.目標(biāo)是最小化滿意度,而滿意度就是最大限度的生產(chǎn)調(diào)度,并給出滿意度的一些定理和最優(yōu)的算法;Fardin[4]利用另外形式的三角形模糊數(shù)討論了具有模糊加工時(shí)間的最大完工時(shí)間,給出了模糊工期的隸屬函數(shù),并給出了模糊工期的一些定義與性質(zhì);Wang[5]討論了單機(jī)并具有到達(dá)時(shí)間的且工期是模糊的一系列問(wèn)題.

本文考慮平行機(jī)具有模糊交貨期下的最大延遲懲罰,并討論關(guān)于在最優(yōu)調(diào)度下的總誤工時(shí)間,給出一些基本性質(zhì)和算法.為此,引入三角形模糊數(shù)運(yùn)算如下:

定義1[2]兩個(gè)三角形模糊數(shù)相等的充要條件是a1=b1,a2= b2,a3=b3.

定義2[2]有兩個(gè)三角形模糊數(shù)(TFNS),則的模糊和為

定義3 若k≥0,k·(a,b,c)=(ka,kb,kc)為三角形模糊數(shù)的數(shù)量乘法.

1 最小化延遲懲罰問(wèn)題

用三角形模糊數(shù)來(lái)表示模糊交貨期.給出經(jīng)典數(shù)和模糊數(shù)相減的方法,經(jīng)典數(shù)和模糊數(shù)相乘的方法,如何比較模糊數(shù)的大小,本節(jié)研究以下兩個(gè)問(wèn)題:

1.1 問(wèn)題描述

設(shè)有工件集J={J1,J2,...,Jn},工件的加工時(shí)間、交貨期和完工時(shí)間分別為pi,和Ci(1≤i≤n),機(jī)器的數(shù)量為2.假設(shè)工件的準(zhǔn)備時(shí)間為rj,并假定:

(1)工件具有不同的準(zhǔn)備時(shí)間;

(2)工件加工允許中斷;

(3)一臺(tái)機(jī)器不能同時(shí)加工兩個(gè)工件;

(4)機(jī)器加工過(guò)程中允許出現(xiàn)空閑;

(5)一個(gè)工件不能同時(shí)在兩臺(tái)機(jī)器上加工;

(6)工件的交貨期是模糊數(shù).

定義4[4]誤工任務(wù)為Tj,其交貨期用三角形模糊數(shù)(TFNs)表示為=(d1j,d2j,d3j),其中d1j代表最優(yōu)值,d2j代表最合理值,d3j代表最差值.

定義5 d1j≤d2j≤d3j,為模糊延誤值,稱為模糊延誤懲罰值.

定義6 對(duì)于誤工任務(wù)為最大模糊延誤懲罰值.

1.2 最大延誤懲罰

對(duì)于每個(gè)任務(wù)Tj∈T都給定了加工時(shí)間pj,準(zhǔn)備時(shí)間rj和交貨期,用三角形模糊數(shù)=(d1j,d2j,d3j)來(lái)表示模糊交貨期.pj≥0,rj≥0且Cj≥0,則的隸屬函數(shù)可以表示為:

t是實(shí)數(shù).若t=Cj則(Cj)表示完工時(shí)間Cj和模糊交貨期之間的關(guān)系.取0≤λ≤1,如果(Cj)＜λ ,則稱Tj為誤工任務(wù),得到下面判斷任務(wù)是否誤工的判斷法則:

對(duì)于Uj=1的任務(wù)Tj,計(jì)算,在計(jì)算的時(shí)候,需要比較的大小.

本文采用文獻(xiàn)[5]提出的三條準(zhǔn)則比較兩個(gè)模糊數(shù)的大小.對(duì)于兩個(gè)三角形模糊數(shù)(TFNS)=(a1,a2,a3),=(b1,b2,b3),

準(zhǔn)則1[5]:若

準(zhǔn)則2[5]:如果(3)中不能夠比較并排序,若

準(zhǔn)則3[5]:如果(3)(4)都不能夠排序兩個(gè)模糊三角數(shù),若a3-a1＜b3-b1,則＜.

這里的EFDD序不一定給出這個(gè)問(wèn)題的最優(yōu)排序.因此考慮一種特殊情況:每個(gè)工件的權(quán)重和模糊交貨期滿足一致性假設(shè),即對(duì)于工件Ji和Jj有wi≤wj?di≤dj.此時(shí)研究問(wèn)題有以下性質(zhì).

引理1 對(duì)于當(dāng)前問(wèn)題,如果每個(gè)工件的權(quán)重與交貨期一致,則存在一個(gè)最優(yōu)序列,使得每個(gè)工件都按照交貨期的EFDD序排列.

證由于每個(gè)工件的權(quán)重和交貨期一致,所以每個(gè)工件的ERD序與EFDD序是一樣的,對(duì)于工件可以采用二交換法證明,設(shè)π1按照ERD和EFDD序排列的一個(gè)最優(yōu)序列,考慮其中的任意兩個(gè)工件i和j,并且給出≤,則wi≤wj.假設(shè)這兩個(gè)工件的開始時(shí)間和完工時(shí)間是兩個(gè)區(qū)間t[1,t1+x]和t[2,t2+x],并且t2＞t1+x,因此i有一個(gè)加工過(guò)程在t[1,t1+x]區(qū)間,并且間隔一段距離后,j在t[2,t2+x]區(qū)間上加工,i的到達(dá)時(shí)間為t1,j的到達(dá)時(shí)間為t2,并且Max{ri,rj}≤t1,工件i與工件j交換位置獲得最新序列π2.

max{Ci(π2),Cj(π2)}-max{Ci(π1),Cj(π1)}=0,Cj(π1)=t2+x,Cj(π2)=t1+x,所以Cj(π2)≤Cj(π1).

定理1 問(wèn)題p 2|rj,prem|max wj能夠在O(n2)時(shí)間內(nèi)得到解決.

《導(dǎo)基》的智慧課堂教學(xué)根據(jù)全國(guó)導(dǎo)游資格考試大綱與題型，對(duì)課程內(nèi)容進(jìn)行合理的智慧構(gòu)建，采用課件講解、圖片、視頻、問(wèn)題、討論、頭腦風(fēng)暴、投屏演示、現(xiàn)場(chǎng)練習(xí)等多種手段強(qiáng)化教學(xué)內(nèi)容，加深學(xué)生們對(duì)知識(shí)點(diǎn)的歸納、辨析與理解，強(qiáng)化對(duì)知識(shí)點(diǎn)的記憶與靈活運(yùn)用，減少測(cè)評(píng)時(shí)出錯(cuò)，提高考證通過(guò)率。

證算法的計(jì)算量主要體現(xiàn)在第一步和第二步上,對(duì)工件的到達(dá)時(shí)間有先到先排的時(shí)候有一個(gè)序列,需要時(shí)間為O(n log n),由于在此基礎(chǔ)上還需要對(duì)工期進(jìn)行排列,需要在O(n log n)時(shí)間內(nèi)解決,所以總的計(jì)算量為O(n2).

引理2 兩個(gè)分別擁有元素xj和yj且個(gè)數(shù)相等的序列,如果這兩個(gè)序列按相反的單調(diào)順序排列,那么對(duì)應(yīng)元素的乘積和最小.

2 總延遲懲罰

考慮平行機(jī)中的總延遲懲罰的問(wèn)題,給出類似算法.

定理2 工件按照ERD序排列,并且交貨期是按照EFDD序排列,得到一個(gè)最優(yōu)排序,能夠求出延誤修正值,然后再根據(jù)準(zhǔn)則1,2,3進(jìn)行比較得到從小到大排序,并且讓權(quán)重按照w1≥w2≥...≥wn,能夠得到最優(yōu)序列使目標(biāo)有最優(yōu)值.

證有引理2可知,利用二交換法能夠求出延誤工件的延誤修正值,并把得出的序列和權(quán)重按照相反的單調(diào)順序能夠得到最優(yōu)解

算法1

步驟1 當(dāng)前到達(dá)工件中按照先到先排,若只有一個(gè)工件到達(dá)時(shí),讓其在任意空閑的機(jī)器上加工;若有兩個(gè)工件到達(dá),讓其在兩臺(tái)機(jī)器上加工;若有多個(gè)任務(wù)到達(dá),應(yīng)用準(zhǔn)則1,2,3對(duì)模糊工期進(jìn)行排序,選出模糊交貨期小的兩個(gè)工件在p1和p2上加工.若兩個(gè)工件的模糊交貨期相等,則按照權(quán)重的w1≥w2≥...≥wn排列.

步驟2 當(dāng)某個(gè)工件加工完畢后,在已經(jīng)到達(dá)的工件中應(yīng)用準(zhǔn)則1、準(zhǔn)則2和準(zhǔn)則3對(duì)模糊交貨期進(jìn)行排序,按照的序列在空閑機(jī)器上加工.若模糊交貨期相等,則按照權(quán)重的w1≥w2≥...≥ wn排列.

步驟3 若又有新工件到達(dá)時(shí),轉(zhuǎn)步驟1;若所有工件都已經(jīng)到達(dá),轉(zhuǎn)步驟4.

步驟4 所有的工件都已到達(dá),對(duì)所有未加工的工件和未加工完的工件應(yīng)用準(zhǔn)則1、準(zhǔn)則2和準(zhǔn)則3按照模糊交貨期不減的順序制表,取表最前的兩個(gè)工件在兩臺(tái)機(jī)器上加工,若有多個(gè)工期相等并最小,則按照wj不增的順序,選取兩個(gè)最前的加工.

3 最小化總誤工問(wèn)題

在上述基礎(chǔ)上,給出算法并算出最小的總延誤模糊修正時(shí)間.工件集合J={J1,J2,...,Jn},在模糊調(diào)度中,模糊工期反映了決策者對(duì)工件的完工時(shí)間的滿意度是逐漸變化的,作為經(jīng)典調(diào)度問(wèn)題的推廣,在模糊調(diào)度中可以定義完工期限和誤工區(qū)域以及可行調(diào)度的概念.

性質(zhì)1 如果有λ＞0,則對(duì)問(wèn)題的任何一個(gè)最優(yōu)調(diào)度π*,①工件Jj不誤工的完工時(shí)間滿足;

②工件Jj誤工的完工時(shí)間滿足;

證①因?yàn)棣耍?,在隸屬函數(shù)中就滿足;

②類似可證明.

性質(zhì)2 若(Cj)=0,則有Cj≥d3j或Cj≤d1j,若是Cj≥d3j,則全部工件都誤工,總誤工會(huì)越大,若Cj≤d1j,則沒(méi)有誤工工件,

證由題意可得,若Cj≥d3j,并且知道d1j≤d2j≤d3j,則有完工時(shí)間大于最大工期,所以通過(guò)判斷法則,所有的工件都誤工.若Cj≤d1j,則有工件完工時(shí)間小于最小工期,則所有工件都不誤工,并且0.

定義7[4]對(duì)給定的滿意度λ(0≤λ≤1),稱:Dj1(λ)=d3j-λ(d3j-d2j),或者有Dj2(λ)= λ(d2j-d1j)+d1j為工件Jj對(duì)應(yīng)于滿意度λ的誤工區(qū)域.即Cj≤Dj2或者Cj≥Dj1都讓工件誤工.

性質(zhì)3 如果對(duì)任何λ(0＜λ＜1),Cj≤D2或者Cj≥D1都不成立,則此時(shí)對(duì)工件集按照EFDD序排列能夠得到最優(yōu)序.

基于以上的分析,給出一算法解決本節(jié)的問(wèn)題:

算法2

步驟1 工件Jj先到的先排,λ(λ≠0)值固定.若d1j≤pj≤d2j,工件集(J1,J2,...,Jn)按照Dj2= λ(d2j-d1j)+d1j的非減的次序依次排在p1和p2機(jī)器上.若d2j≤pj≤d3j,則Dj1(λ)=d3jλ(d3j-d2j)的非增序列依次排在p1和p2機(jī)器上.

步驟2 當(dāng)λ=0;工件集按照先到先排,并利用準(zhǔn)則1、準(zhǔn)則2、準(zhǔn)則3來(lái)比較模糊工期的大小,并按照工期小的先排,算出∑jTj.

4 結(jié)束語(yǔ)

本文討論了平行機(jī)具有模糊工期的最大延遲懲罰和總誤工的一些相關(guān)問(wèn)題,目標(biāo)是怎樣排序能夠使最大延遲懲罰最小,并且也討論了使總誤工最優(yōu)的排序.對(duì)其他模型的討論和其他機(jī)器環(huán)境下的排序問(wèn)題有待進(jìn)一步的研究.

[1]Prade H.Using Fuzzy Set Theory in a Scheduling problem:A Case Study[J].Fuzzy Sets and Systems,1979,2(2):153-165.

[2]霍錄景,米洪海.具有模糊交貨期的平行機(jī)排序問(wèn)題[J].科學(xué)技術(shù)與工程,2010,10(29):7223-7225.

[3]袁芬,谷云東,塵非.關(guān)于模糊工期平行機(jī)調(diào)度問(wèn)題的若干結(jié)果[J].北京師范大學(xué)學(xué)報(bào),2006,42(3):232-235.

[4]Fardin Ahmadizar,Leila Hosseini.Minimizing makespan in a single-machine scheduling problem with a learning effect and Fuzzy processing times[J].Int J Adv Manuf Technol,2013,65:581-587.

[5]Wang C,Wang D,Ip WH,et al.The single machine ready time scheduling problem with fuzzy processing times[J].Fuzzy Set Systems,2002,127:117-129.

[6]劉春來(lái),趙傳立.工期窗口安排與具有退化效應(yīng)和維修活動(dòng)的單機(jī)排序[J].數(shù)學(xué)實(shí)踐與認(rèn)識(shí),2012,42(11):122-130.

[7]吳會(huì)江.一種具有模糊交貨期的單機(jī)調(diào)度問(wèn)題[J].科學(xué)技術(shù)與工程,2005,5(9):592-593.

[8]Fardin Ahmadizar,Leila Hosseini.Single machine scheduling with a position-based learning effect and fuzzy processing times[J].Int J Adv Manuf Technol,2011,56:693-698.

[9]Ahmadizar F,Ghazanfari M,Fatemi Ghomi SMT.Application of chance-constrained programming for stochastic group shop scheduling problem[J].Int J Adv Manuf Technol,2009,142:321-334.

[10]Orcun S,Altinel IK,Hortascu O.scheduling of batch processes with operational uncertainties[J].Compution Chem Eng,1996,20:S1191-S1196.

[11]Liu B,Liu YK.Expected value of fuzzy variable and fuzzy expected value models[J].IESS Trans Fuzzy Systems,2002,10:445-450.

With fuzzy due dates penalties and parallel machine scheduling problems

YE Caihong

(College of Mathematics,Chongqing Normal University,Chongqing 401331,China)

Consider having a parallel machine scheduling problem with fuzzy due dates,discussed the scheduling problem with due dates and total tardiness problem,using the triangle in the model of fuzzy number to the due date that come out,and have time to prepare,and the work piece is allowed to interrupt,the goal is to have an optimal sequence to get the maximum tardiness penalty,with satisfaction to discuss the total tardiness,and obtain the optimal scheduling to minimize the total tardiness,to these problems the algorithm.

scheduling;fuzzy lead time;triangle fuzzy number;preparation time;satisfaction

O223;C93

:A

:1671-9476(2015)05-0009-0005

10.13450/j.cnki j.zknu.2015.05.003

2014-11-20;

:2015-03-30

國(guó)家自然科學(xué)基金(No.61302180);中國(guó)博士后基金面上資助項(xiàng)目(No.2013M540698);重慶市科委自然科學(xué)基金(No.cstc2014jcyj A0003);重慶市教委自然科學(xué)基金(No.KJ130606);重慶師范大學(xué)重點(diǎn)項(xiàng)目(No.2011XLZ05)

葉彩虹(1990-),女,四川達(dá)州人,碩士研究生,研究方向:排序論.