[緊急] 排班演算法

前陣子寫了一個case,如下網站:

http://robot101.blogspot.com/

是一個郵政排班系統,每個人都有負責的區域(1~6個),這一生當中只會排這些區域。

而一天中,除了休假,還有特別排班(即是那個人那天就分配特定區域)之外,其餘的人每個人負責一個區域。

簡單來說,如果有56個區域,就有56個人負責,每個人負責區域不同。

 

演算法真的很難想,我想過各種方法,最後使用暴力法,就是每種狀況都去測試。可是問題來了!幸運的話,幾分鐘就排出來,如果很慘的話可能要跑上好幾個小時都不一定有結果。原因是總共有67個人,而我要測試6的67次方之多...這是很恐怖的數字,導致效率真是奇差無比。

請問有哪位大大有想到更好的方法碼嗎QQ?我願意給他我所有的IT幣,雖然只有48元QQ

如果可以的話就請將你說的這部份程式的演算法上傳,大家可以互相研究

LabVIEW.rar

裡面有Excel檔,禮拜一要用電腦排排看,禮拜二是手工排好的。

暴力法是我寫的程式:(

如何操作你的程式,可否簡單說明一下

????? Folder.rar

OK,試試看這個!我把一些基礎的數值都default了

我程式功力太弱,幫不上忙,不過進來幫你加油打氣一下^^
有個小建議,6的67次方太大了!
那如果是67的6次方會不會比較好一點呢?
還有,排過的地方不是就能去掉,不用再比對了嗎?
因為程式我不大行,不知道是不是可行。
希望對你有幫助,加油

我的用意也是拋磚引玉,看是否有邏輯分析強的人可以幫忙

囧...

這樣排序的和資料庫會有關係嗎?

K大,小弟為8.2版,所以只能從敘述中來和了解問題

暴力法是否為將6個區域進行67個人的尋找,所以總共要667次方的尋找

小弟的想法與 iamcary 類似,是否可以將已尋找過的範圍作惕除

這樣子尋找的範圍與次數會越來越小

 

另外,小弟有找到搜尋的演算法網頁

K大可以參考與討論哦

http://www.chwa.com.tw/TResource/HS/book2/ch7/7-5.htm

elvistu40404.0094560185

感謝各位的想法XD,我想變成6的67次方還是很大

我是有寫過弄掉就刪除,可是會有一些情況排不出來

XD有誰想要接此案的吧!我可以幫你跟顧客牽線一下...

因為雇主也很急XD

真有趣 我來試試看

你想試試看嗎?

版本不同沒辦法改…

給點之前做類似案件的建議:

0. 初始化變數
1. 列出每個人所可能負責的全部區域清單
2. 計算每個區域負責的人數,若有區域無人負責,則重新計算
3. 以最少人負責的區域,隨機抽一個人負責該區域
4. 若同時有多數最少人負責的區域,隨機抽一個區域執行第3項
5. 將已分配的人移出清單
6. 重複執行1-5項,直到所有人數安排完

其中針對演算時間比較有影響的是:
1. 盡可能採用隨機,固定方式推論容易造成多餘演算
2. 無需最佳化,意味著只需要找最少人負責的區域,不要再多找負責最少區域的人,容易流於固定演算,反而難求到答案
    (因為規則都一樣,每次演算都要跑相同流程)
3. 雖然遞迴是神的技巧,但是有時候容易陷入迷思,反而浪費時間

跟你原本的作法雷同,但是刪除一些東西或許會能更快得到答案,參考看看^^?


這是個很棒的題目~只是小弟還是看不太懂

56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂

是要操死他呢~~還是說過太爽

可以解釋一下嗎

根據knightsoul的Excel檔,展開成區域vs.可出勤人員的交叉表,並計算每個區域可用人數,以及每個人可負責區域數,手動進行排班作業後,提供個人一點淺見:

其演算法則中,有固定優先順序部份(只要每個區域負責人數大於0,必定有解):

1.必須從負責人數最少的區域開始分派(人數少->人數多)。

2.一個區域排除已分配者後,需從負責最少區域數的人開始分派。

無優先順序,可隨機分派部份(隨機選定區域或人員時,可衍生多種解):

1.相同負責人數的區域中,可隨機選擇區域進行分派。

2.某區域可分派人員其負責區域數最少者,有超過1人時。

 

 

@caeru

其實我之前用過隨機的方式去搜尋,可是其實效果也不太好,我有考慮到人數最少的先排,區域最少的先排。

但是效果都不太好

最大的問題莫過於區域最少人的排完之後,其他的區域其實人數都差不多。

[QUOTE=NewHandAlex]

這是個很棒的題目~只是小弟還是看不太懂

56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂

是要操死他呢~~還是說過太爽

可以解釋一下嗎

[/QUOTE]


小弟的認知如下(不知道是否正確)..
題目意思為:

每個人有負責的區域,所以56個區域會有56個人負責
如果當天因為有某些人員休假時,就會有其他幾個人來頂休假人的區域,也就是特別排班的意思
若有錯誤,再麻煩K大修正一下

elvistu40407.8813657407

[QUOTE=elvistu][QUOTE=NewHandAlex]

這是個很棒的題目~只是小弟還是看不太懂

56個區域有56個人負責~可是一個人又要負責1~6的區域<==============這裡不是很懂

是要操死他呢~~還是說過太爽

可以解釋一下嗎

[/QUOTE]


小弟的認知為(不知道是否正確)
每個人有負責的區域,所以56個區域會有56個人負責
如果當天因為有某些人員休假時,就會有其他幾個人來頂休假人的區域,也就是特別排班的意思
若有錯誤,再麻煩K大修正一下

[/QUOTE]

大致上都正確,只有特別排班的地方XD

特別排班的意思是指說主管就是要某人安排哪些區域,而這些區域可能不會在他負責區域裡。

簡單來說,特別區域只是主管指定某人某區域而已。

有哪些先進有特別的想法了嗎?

[QUOTE=knightsoul]

最大的問題莫過於區域最少人的排完之後,其他的區域其實人數都差不多。

[/QUOTE]

請教一下,K大說明這樣子的結果,算是不好的排法嗎??