裝配線平衡模型 一條裝配線含有一系列的工作站

1、裝配線平衡模型裝配線平衡模型一條裝配線含有一系列的工作站，在最終產(chǎn)品的加工過(guò)程中每個(gè)工作站執(zhí)行一種或幾種特定的任務(wù)。裝配線周期是指所有工作站完成分配給它們各自的任務(wù)所化費(fèi)時(shí)間中的最大值。平衡裝配線的目標(biāo)是為每個(gè)工作站分配加工任務(wù)，盡可能使每個(gè)工作站執(zhí)行相同數(shù)量的任務(wù)，其最終標(biāo)準(zhǔn)是裝配線周期最短。不適當(dāng)?shù)钠胶庋b配線將會(huì)產(chǎn)生瓶頸——有較少任務(wù)的工作站將被迫等待其前面分配了較多任務(wù)的工作站。問(wèn)題會(huì)因?yàn)楸姸嗳蝿?wù)間存在優(yōu)先關(guān)系而變得更復(fù)雜，任務(wù)的

2、分配必須服從這種優(yōu)先關(guān)系。這個(gè)模型的目標(biāo)是最小化裝配線周期。有2類(lèi)約束：①要保證每件任務(wù)只能也必須分配至一個(gè)工作站來(lái)加工；②要保證滿(mǎn)足任務(wù)間的所有優(yōu)先關(guān)系。例有11件任務(wù)（A—K）分配到4個(gè)工作站（1—4），任務(wù)的優(yōu)先次序如下圖。每件任務(wù)所花費(fèi)的時(shí)間如下表。任務(wù)ABCDEFGHIJK時(shí)間4511950151212121289MODEL:!裝配線平衡模型SETS:!任務(wù)集合，有一個(gè)完成時(shí)間屬性TTASKABCDEFGHIJK:T!任務(wù)之間

3、的優(yōu)先關(guān)系集合（A必須完成才能開(kāi)始B，等等）PRED(TASKTASK)ABBCCFCGFJGJJKDEEHEIHJIJ!工作站集合STATION1..4TXS(TASKSTATION):X!X是派生集合TXS的一個(gè)屬性。如果X（I，K）＝1，則表示第I個(gè)任務(wù)指派給第K個(gè)工作站完成ENDSETSDATA:!任務(wù)ABCDEFGHIJK的完成時(shí)間估計(jì)如下T=4511950151212121289ENDDATA!當(dāng)任務(wù)超過(guò)15個(gè)時(shí)，模型的求解

4、將變得很慢!每一個(gè)作業(yè)必須指派到一個(gè)工作站，即滿(mǎn)足約束①@F(TASK(I):@SUM(STATION(K):X(IK))=1)!對(duì)于每一個(gè)存在優(yōu)先關(guān)系的作業(yè)對(duì)來(lái)說(shuō)，前者對(duì)應(yīng)的工作站I必須小于后者對(duì)應(yīng)的工作站J，即滿(mǎn)足約束②@F(PRED(IJ):@SUM(STATION(K):KX(JK)KX(IK))=0)!對(duì)于每一個(gè)工作站來(lái)說(shuō)，其花費(fèi)時(shí)間必須不大于裝配線周期@F(STATION(K):@SUM(TXS(IK):T(I)X(IK))

5、=CYCTIME)!目標(biāo)函數(shù)是最小化轉(zhuǎn)配線周期(A)(B)(C)(F)(G)(K)(J)(I)(H)(E)(D)X(K3)0.0000009.000000X(K4)1.0000000.000000二次分配問(wèn)題（二次分配問(wèn)題（QuadraticQuadraticAssignmentAssignmentProblemProblem）這個(gè)問(wèn)題是指派問(wèn)題的一種推廣?？梢园阎概蓡?wèn)題看作線性規(guī)劃問(wèn)題，故較易求解，而二次分配問(wèn)題是純整數(shù)規(guī)劃問(wèn)題，往往

6、很難求解。與分配問(wèn)題一樣，二次分配問(wèn)題也與兩個(gè)目標(biāo)集合S、T有關(guān)。S和T含有相同數(shù)目的元素，以便達(dá)到某一目標(biāo)。這里兩種必須滿(mǎn)足的條件：必須把S的每個(gè)元素確切地分配給T的一個(gè)元素；T的每個(gè)元素只能接受S的一個(gè)元素?？梢?1變量：????其它的一個(gè)元素）（的一個(gè)元素）分配給（把01TjSixij。用和分配問(wèn)題相同的約束條件給出以上兩個(gè)條件：njxnixniijnjij21121111??????????，但是本問(wèn)題的目標(biāo)比分配問(wèn)題的更加復(fù)

7、雜。我們得到的價(jià)格系數(shù)ijklc，其解釋是：在i（S的一個(gè)元素）分配給j（T的一個(gè)元素）的同時(shí)把k（S的一個(gè)元素）分配給l（T的一個(gè)元素）所應(yīng)承擔(dān)的費(fèi)用。顯然，只有當(dāng)1?ijx且1?klx，即其乘積1?klijxx時(shí)，才承擔(dān)這種費(fèi)用。于是本目標(biāo)變成一個(gè)01變量的二次表達(dá)式：????????ninjnknlklijijklxxc1111。最常見(jiàn)的是系數(shù)ijklc從其它系數(shù)ikt和jld的乘積推出來(lái)的情況：jlikijkldtc?。為了弄清

8、這個(gè)相當(dāng)復(fù)雜的模型，研究下面兩個(gè)應(yīng)用是有好處的。首先認(rèn)為S是一個(gè)n個(gè)工廠的集合，T是一個(gè)n個(gè)城市的集合。本問(wèn)題就是要在每一城市中設(shè)置一個(gè)工廠，并要使工廠之間總的通訊費(fèi)用最小。通訊費(fèi)用取決于（1）每對(duì)工廠之間通訊的次數(shù)；（2）每對(duì)工廠所在兩個(gè)城市之間的距離。顯然，有些工廠很少與別的工廠通訊，雖相距甚遠(yuǎn)而費(fèi)用卻不大。另一方面，有些工廠可能需要大量通訊。通訊費(fèi)取決于距離的遠(yuǎn)近。在這個(gè)應(yīng)用中，ikt表示工廠i和工廠k之間的通訊次數(shù)（以適當(dāng)?shù)膯挝?/p>

9、計(jì)量）；jld為城市j和城市l(wèi)之間每單位的通訊費(fèi)用（顯然這與j和l之間的距離有關(guān)）。如果工廠i和k分別設(shè)在城市j和l，顯然這兩家間的通訊費(fèi)由jlikijkldtc?來(lái)確定。因而總費(fèi)用可用上述目標(biāo)函數(shù)來(lái)表示。有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)都必須首先找公司秘書(shū)初試，然后到部門(mén)主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專(zhuān)業(yè)背景不同，所以每人在三個(gè)階段的面