多目標(biāo)最短時(shí)限指派問題的算法探析

文/李 敏

標(biāo)準(zhǔn)指派問題只要求使得總時(shí)間最少。但實(shí)際很多指派問題既要求總時(shí)間最少，還要求在最短時(shí)間內(nèi)完成。 這類問題被稱為最短時(shí)限指派問題，如搶險(xiǎn)(搶修)任務(wù)的指派問題等。目前，對(duì)它的研究較少且主要是研究單目標(biāo)問題，常用算法有簡(jiǎn)算法[1]、最短時(shí)限逼近法[2]等。本文研究的是多目標(biāo)問題，給出了在簡(jiǎn)算法的基礎(chǔ)上通過對(duì)匈牙利算法中尋找獨(dú)立零元素的次序進(jìn)行改進(jìn)的新算法。

一、多目標(biāo)最短時(shí)限指派問題的數(shù)學(xué)模型

多目標(biāo)最短時(shí)限指派問題：設(shè)有n項(xiàng)工作指派給n個(gè)人去做，要求一人一事且一事一個(gè)。已知第i人做第j項(xiàng)工作的時(shí)間為cij，如何分配工作，才能使在最短時(shí)間內(nèi)完成任務(wù)的前提下使總時(shí)間最少。令決策變量xij=1，第i人去做工作j；否則xij=0。則其數(shù)學(xué)模型為：

二、多目標(biāo)最短時(shí)限指派問題的求解

(一)多目標(biāo)最短時(shí)限指派問題的轉(zhuǎn)化

首先考慮目標(biāo)函數(shù)(1)，再考慮目標(biāo)函數(shù)(2)。假設(shè)(1)的最優(yōu)解為F，則多目標(biāo)規(guī)劃模型(1)～(3)可以轉(zhuǎn)化為如下的單目標(biāo)模型：

(二)算法思想及步驟

簡(jiǎn)算法是求解單目標(biāo)最短時(shí)限的算法，它可求出完成任務(wù)的最短時(shí)限，但卻不一定使時(shí)間總和達(dá)到最優(yōu)。本算法的思想為：首先找到指派的最短時(shí)限，即目標(biāo)(1)的最優(yōu)解F1，則C中一定存在n個(gè)獨(dú)立且不大于F1的元素，故只要它們的和最小即可。步驟如下：

Step2 將時(shí)間矩陣C中不大于F1的元素全部變?yōu)?，并記為矩陣C(F1)。

Step3 若矩陣C(F1)中某行(列)中的零元素既行獨(dú)立，又列獨(dú)立，則選中它，并劃掉它所在的行和列。若C(F1)中某列(行)存在多個(gè)獨(dú)立零，則在它們的行(列)中找出各自的次小元素，選中次小值最大的行(列)中的獨(dú)立零，劃掉它所在的行和列。若上述情況不止一種，則優(yōu)先分配次小元素最大的行或列中的獨(dú)立零。若C(F1)中所有的行(列)都無(wú)獨(dú)立零元素，則任意選出零元素最少的行(列)中的一個(gè)零(多數(shù)禮讓少數(shù))。

Step4 如選中n個(gè)獨(dú)立零元素，則令它們對(duì)應(yīng)的變量為1，其它變量為0，即得最優(yōu)指派解；否則，轉(zhuǎn)Step5。

Step5 取 F2=min{cij|cij＞F1, i, j=1,2,…, n}，用F2代替F1，轉(zhuǎn)Step2。

三、算例

例 已知某多目標(biāo)最短時(shí)限指派問題的時(shí)間矩陣為：

解由Step1 得，F(xiàn)1=18。將C中不大于F1的元素全部變?yōu)?，得矩陣

可見只選中了3個(gè)獨(dú)立零元素，故轉(zhuǎn)Step5。計(jì)算得F2=19，同理得矩陣

顯然，已找到該指派問題的最優(yōu)解，相應(yīng)的F=19，Z=70。通過比較發(fā)現(xiàn)，本算法所用總時(shí)間比文獻(xiàn)[1]要少個(gè)單位，本算法的計(jì)算結(jié)果與文獻(xiàn)[3]一致，且計(jì)算要簡(jiǎn)單得多。

通過比較可知該算法操作簡(jiǎn)單，對(duì)于小規(guī)模指派問題可以手工操作，對(duì)于大規(guī)模指派問題可編程實(shí)現(xiàn)，因此具有較強(qiáng)的可操作性和適用性。

[1]白國(guó)仲.線性不可微規(guī)劃—基于可持續(xù)發(fā)展的決策技術(shù)[M].北京：中國(guó)社會(huì)科學(xué)出版社，2007.

[2]夏少剛，費(fèi)威.基于最小調(diào)整法求解最短時(shí)限指派問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39(17)：179-187.

[3]韓艷娜，郭東威.多目標(biāo)線性不可微指派問題的優(yōu)化算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(xué)漢文版)，2017，46(3)：325-328，333.