葉彩虹

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

具有模糊交貨期并賦有延遲懲罰的平行機排序問題

葉彩虹

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

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

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

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

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

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

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

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

1 最小化延遲懲罰問題

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

1.1 問題描述

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

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

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

(3)一臺機器不能同時加工兩個工件;

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

(5)一個工件不能同時在兩臺機器上加工;

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

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

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

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

1.2 最大延誤懲罰

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

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

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

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

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

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

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

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

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

證由于每個工件的權(quán)重和交貨期一致,所以每個工件的ERD序與EFDD序是一樣的,對于工件可以采用二交換法證明,設(shè)π1按照ERD和EFDD序排列的一個最優(yōu)序列,考慮其中的任意兩個工件i和j,并且給出≤,則wi≤wj.假設(shè)這兩個工件的開始時間和完工時間是兩個區(qū)間t[1,t1+x]和t[2,t2+x],并且t2＞t1+x,因此i有一個加工過程在t[1,t1+x]區(qū)間,并且間隔一段距離后,j在t[2,t2+x]區(qū)間上加工,i的到達時間為t1,j的到達時間為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 問題p 2|rj,prem|max wj能夠在O(n2)時間內(nèi)得到解決.

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

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

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

2 總延遲懲罰

考慮平行機中的總延遲懲罰的問題,給出類似算法.

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

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

算法1

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

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

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

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

3 最小化總誤工問題

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

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

②工件Jj誤工的完工時間滿足;

證①因為λ＞0,在隸屬函數(shù)中就滿足;

②類似可證明.

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

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

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

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

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

算法2

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

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

4 結(jié)束語

本文討論了平行機具有模糊工期的最大延遲懲罰和總誤工的一些相關(guān)問題,目標(biāo)是怎樣排序能夠使最大延遲懲罰最小,并且也討論了使總誤工最優(yōu)的排序.對其他模型的討論和其他機器環(huá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].科學(xué)技術(shù)與工程,2010,10(29):7223-7225.

[3]袁芬,谷云東,塵非.關(guān)于模糊工期平行機調(diào)度問題的若干結(jié)果[J].北京師范大學(xué)學(xué)報,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]劉春來,趙傳立.工期窗口安排與具有退化效應(yīng)和維修活動的單機排序[J].數(shù)學(xué)實踐與認識,2012,42(11):122-130.

[7]吳會江.一種具有模糊交貨期的單機調(diào)度問題[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

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

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