最快需要花多久的時間?─工業工程的實務應用

有個長袖善舞的老闆,平常都靠著身上配戴的三支手機在接生意,為了讓生意不中斷,他必須讓手機時時刻保持在最佳狀態。有一天,他臨時必須到沒有電源的山上去(偏偏這時行動電源還沒有發明出來)。假設每支手機充飽電,需要一個小時,但目前只有兩個充電器,如果要將三支手機都充電充到飽,請問,最快需要花多久的時間?

這個問題是改寫自「國際運算思維挑戰賽」中的一個題目,有些人在看到這個問題時,通常會採取「先到先服務法(First-Come First-Served, FCFS)」,也就是等到兩支手機都充飽電之後,再充下一支,這樣充電的時間是兩小時。

不過,這樣的想法並非最佳解,最佳的答案是先將兩支手機充電各半個小時,然後先拿開一支手機,暫時不要充電,同時另一支手機則繼續充電。此時,再將另外一支還沒充過電的手機拿來充電半小時。等到其中一支手機充電充飽之後,再將原本充好一半電的那支手機,拿回來充飽。就這樣,經過一個半小時之後,三支手機都充飽了電。

以上兩種做法,一種花費兩個小時,一種花費一個半小時。

其實上述問題,屬於工業工程中的「排程」演算法。一般來說,常見的排程演算法有以下四種:

舉例來說,A、B、C三人在排隊影印,所需的時間分為A:5分鐘;B:15分鐘;C:1分鐘。

1.先到先服務法(First-Come First-Served Scheduling)

顧名思義,哪一項工作先進來,就先做那一項。

採「先到先服務法」,服務順序為A、B、C,如圖1所示。這時平均完成時間為(A5分鐘+B20分鐘+C21分鐘)/3=15.3。

圖1. 先到先服務法

2.最短工作優先法(Shortest-Job-First Scheduling)

顧名思義,哪一項工作最短,就先做那一項。

採「最短工作優先法」,服務順序為C、A、B,如圖2所示。這時平均完成時間為(C1分鐘+A16分鐘+B21分鐘)/3=12.6。

圖2. 最短工作優先法

3.優先權排程法(Priority Scheduling)

顧名思義,先做優先順序高的那一項。

採「優先權排程法」,假設服務的優先順序為B、C、A,如圖3所示。這時平均完成時間為(B15分鐘+C16分鐘+A21分鐘)/3=17.3。

圖3. 優先權排程法

4.輪流排程法(Round-Robin Scheduling)

顧名思義,每隔一段時間,處理不同的項目。

採「輪流排程法」,假設輪流服務時間為5分鐘,順序依序為A、B、C、B、B,如圖4所示。這時平均完成時間為(A5分鐘+B47分鐘+C11分鐘)/3=21。

圖4. 輪流排程法

回到一開始的手機充電問題,因為有兩台充電器,但每個電池充完電需要一個小時,亦即每項工作的時間是一樣的,而且沒有優先順序。因此,在選擇排程方法上,可以先排除「最短工作優先法」與「優先權排程法」。

所以,先透過「先到先服務法」計算充電時間,共兩小時,再透過「輪流排程法」,計算出每半小時輪流充電一次,共計一個半小時。這時,就可以得出最快需要一個半小時就能充滿電。

作者:羅凱揚(台科大企管系博士)、蘇宇暉(台科大管研所博士候選人)

繪圖者:謝瑜倩

更多商普好文推薦

精準推薦是否真的有效?

精準推薦是否真的有效? 人工智慧已經應用在許多電商網站。當我們登入會員後,網站往往會根據我們先前的購物資料,再對比這次的購物清單後,推薦最可

閱讀更多 »
回到頂端