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

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

這個問題是改寫自「國際運算思維挑戰賽」中的一個題目，有些人在看到這個問題時，通常會採取「先到先服務法（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。

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

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

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

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

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

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

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

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

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

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

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

作者：羅凱揚（台科大企管系博士）、蘇宇暉（台科大管研所博士候選人）

繪圖者：謝瑜倩