面試時(shí)間優(yōu)化安排

一：提出問題：

問題是這樣產(chǎn)生的：

有4名同學(xué)到一家公司參加三個(gè)階段的面試，公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)〔即：在任何一個(gè)階段4名同學(xué)的順序是一樣的〕，由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如下表所示：〔單位：分鐘〕

秘書初試

主管復(fù)試

經(jīng)理面試

同學(xué)甲

同學(xué)乙

同學(xué)丙

同學(xué)丁

這四名同學(xué)約定他們?nèi)棵嬖囃瓿梢院笠黄痣x開公司，假定現(xiàn)在時(shí)間食早晨8：00，問他們最早何時(shí)能離開公司？

可以看到，這個(gè)例子是日常生活中常見的，尤其是還有一年就要畢業(yè)的我們，面試是找工作時(shí)必不可少的一個(gè)環(huán)節(jié)，幾個(gè)好朋友相約一同面試這樣的問題是極有可能發(fā)生的，所以提出了這樣的一個(gè)問題：好朋友約定全部面試完畢后一同離開公司，那么，如何來安排面試的順序呢？

在當(dāng)今這個(gè)節(jié)約型社會(huì)，一切都提倡綠色，節(jié)約，重復(fù)利用；那么如何來最大限度地縮短總面試的時(shí)間來到達(dá)我們節(jié)約型社會(huì)所提出的要求呢？我們從安排面試時(shí)間這個(gè)小小的問題來看吧，從表中的數(shù)據(jù)，我們隨手算算便可以看到面試順序的不同，最終造成的面試總時(shí)間也是有長(zhǎng)有短的。這個(gè)問題有點(diǎn)類似于小時(shí)候遇到的燒開水的問題，是時(shí)間統(tǒng)籌的一種簡(jiǎn)單應(yīng)用。

二：?jiǎn)栴}的分析：

按照公司給出的要求，四名求職者的順序一旦確定以后，在秘書初試、主管復(fù)試、經(jīng)理面試各階段中面試的順序?qū)⒉辉俑淖?，由于每個(gè)求職者在三個(gè)階段面試的時(shí)間不同〔且固定〕，我們考慮對(duì)任意兩名求職者P、Q，不妨設(shè)按P在前，Q在后的順序進(jìn)行面試，可能存在以下兩種情況：

〔一〕、當(dāng)P進(jìn)行完一個(gè)階段j的面試后，Q還未完成前一階段j-1的面試，所以j階段的考官必須等待Q完成j-1階段的面試后，才可對(duì)Q進(jìn)行j階段的面試，這樣就出現(xiàn)了考官等待求職者的情況。這一段等待時(shí)間必將延長(zhǎng)最終的總時(shí)間。

〔二〕、當(dāng)Q完成j-1的面試后，P還未完成j階段的面試，所以，Q必須等待P完成j階段的面試后，才能進(jìn)入j階段的面試，這樣就出現(xiàn)了求職者等待求職者的情況。同樣的，這個(gè)也會(huì)延長(zhǎng)面試的總時(shí)間。

以上兩種情況，必然都會(huì)延長(zhǎng)整個(gè)面試過程。所以要想使四個(gè)求職者能一起最早離開公司，即他們所用的面試時(shí)間最短，只要使考官等候求職者的時(shí)間和求職者等候求職者的時(shí)間之和最短，這樣就使求職者和考官的時(shí)間利用率到達(dá)了最高。他們就能以最短的時(shí)間完成面試一起離開公司。這也是我們想要的結(jié)果。

從這個(gè)問題中我們可以聯(lián)想到該問題涉及的面試時(shí)間與人數(shù)有一定關(guān)系，假設(shè)想節(jié)省時(shí)間，很值得推廣。發(fā)散地考慮，大多數(shù)工廠的流水線的裝配也有類似的思想，所以這樣的一個(gè)模型很有推廣的意義。

三：模型假設(shè)：

1.我們假設(shè)參加面試的求職者都是平等且獨(dú)立的，即他們面試的順序與考官無關(guān)；

2.面試者由一個(gè)階段到下一個(gè)階段參加面試，其間必有時(shí)間間隔，但我們?cè)谶@里假定該時(shí)間間隔為0；

3.參加面試的求職者事先沒有約定他們面試的先后順序；

4.假定中途任何一位參加面試者均能通過面試，進(jìn)入下一階段的面試。即：沒有中途退出面試者；

5.面試者及各考官都能在8：00準(zhǔn)時(shí)到達(dá)面試地點(diǎn)。

四：模型建立：

決策變量：

記tij

為第i名同學(xué)參加第j階段面試需要的時(shí)間〔見表〕，令xij

表示第i名同學(xué)參加第j階段面試的開始時(shí)刻〔在這里我們不妨記早上8：00面試開始時(shí)間為0時(shí)刻〕〔i=1，2，3，4；j=1，2，3〕顯然它們都應(yīng)當(dāng)是非負(fù)整數(shù)。

決策目標(biāo)：

第三階段面試的開始時(shí)間+第三階段面試的時(shí)間T=Max{

xij

+tij}〔j=3〕，求出T的最小值即是我們最終想要優(yōu)化的目標(biāo)。

約束條件：

1）

時(shí)間先后次序約束，即是說每個(gè)人只有參加完前一個(gè)階段的面試后才能進(jìn)入下一個(gè)階段；

Xij+tij<=Xij+1〔i=1，2，3，4；j=1，2，3〕

2〕每個(gè)階段j同一時(shí)間只能面試1名同學(xué)：用0-1變量yik表示第k名同學(xué)是否排在第i名同學(xué)前面〔1表示是，0表示否〕

那么有：

Xij+tij-xkj<=T*yik

(i,k=1,2,3,4;j=1,2,3;i<=k)

Xkj+tkj-Xij<=T*(1-yik)

(i,k=1,2,3,4;j=1,2,3;i<=k)

于是我們的目標(biāo)函數(shù)為：

Min

T；

T=Max{

xij

+tij}；

連同約束條件，輸入LINGO求解：

代碼如下：

model:

min=T;

x41+8

x42+10

x31+20

x32+16

x21+10

x22+20

x11+13

x12+15

T>x43+15;

T>x33+10;

T>x23+18;

T>x13+20;

x31+20-x41

x32+16-x42

x33+10-x43

x21+10-x31

x22+20-x32

x23+18-x33

x21+10-x41

x22+20-x42

x23+18-x43

x11+13-x21

x12+15-x22

x13+20-x23

x11+13-x31

x12+15-x32

x13+20-x33

x11+13-x41

x12+15-x42

x13+20-x43

x41+8-x31

x42+10-x32

x43+15-x33

x41+8-x21

x42+10-x22

x43+15-x23

x31+20-x21

x32+16-x22

x33+10-x23

x21+10-x11

x22+20-x12

x23+18-x13

x31+20-x11

x32+16-x12

x33+10-x13

x41+8-x11

x42+10-x12

x43+15-x13

@bin(y34);@bin(y12);@bin(y13);@bin(y14);

@bin(y23);@bin(y24);

end

得到：

Local

optimal

solution

found

at

iteration:

3104

Objective

value:

84.00000

Variable

Value

Reduced

Cost

T

84.00000

0.000000

X41

0.000000

0.9999970

X42

9.500000

0.000000

X43

21.00000

0.000000

X31

32.50000

0.000000

X32

58.00000

0.000000

X33

74.00000

0.000000

X21

22.50000

0.000000

X22

36.00000

0.000000

X23

56.00000

0.000000

X11

8.000000

0.000000

X12

21.00000

0.000000

X13

36.00000

0.000000

Y34

1.000000

0.000000

Y23

0.000000

-83.99950

Y24

1.000000

0.000000

Y12

0.000000

-83.99950

Y13

0.000000

0.000000

Y14

1.000000

83.99950

Row

Slack

or

Surplus

Dual

Price

84.00000

-1.000000

1.500000

0.000000

1.500000

0.000000

5.500000

0.000000

0.000000

0.000000

3.500000

0.000000

0.000000

0.9999970

0.000000

0.9999970

0.000000

0.000000

48.00000

0.000000

0.000000

-0.9999970

10.00000

0.000000

28.00000

0.000000

31.50000

0.000000

19.50000

0.000000

21.00000

0.000000

0.000000

0.000000

2.000000

0.000000

0.000000

0.9999970

51.50000

0.000000

37.50000

0.000000

31.00000

0.000000

1.500000

0.000000

0.000000

0.9999970

0.000000

0.000000

11.50000

0.000000

22.00000

0.000000

18.00000

0.000000

63.00000

0.000000

57.50000

0.000000

49.00000

0.000000

24.50000

0.000000

38.50000

0.000000

38.00000

0.000000

14.50000

0.000000

16.50000

0.000000

20.00000

0.000000

54.00000

0.000000

46.00000

0.000000

56.00000

0.000000

59.50000

0.000000

49.00000

0.000000

46.00000

0.000000

39.50000

0.000000

31.00000

0.000000

36.00000

0.000000

0.000000

0.9999970

1.500000

0.000000

0.000000

0.000000

即所有面試完成需要84分鐘，最正確面試順序安排為丁-甲-乙-丙。

數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

周蕓聰