Unrelated parallel-machine scheduling simultaneously with rate-modifying activities and earliness and tardiness penalties

Abstract

In this paper, we consider a scheduling problem simultaneously with rate-modifying activities and earliness and tardiness penalties on an unrelated parallel-machine setting. We assume that each machine has at most one rate-modifying activity to improve its production efficiency during the scheduling horizon and all the jobs have a common due-date. The objective is to determine jointly the optimal positions of rate-modifying activities, the optimal common due-date of all jobs, and the optimal schedule to minimize the sum of earliness and tardiness costs. We show that the problem can be optimally solved in polynomial time.

本研究探討具維修及提早完工與延遲完工懲罰之非相關平行機台(unrelated parallel-machine)生產排程問題。 本研究假設所有工作具有一個共同之交貨時間點(common due-date) ， 且每一台機器在加工過程中均可至多執行維修(rate-modifying activity)一次 ， 以改善其生產效率。 本研究之目的在尋找最佳維修位置、 最佳共同交貨時間點及最佳工作排序 ， 使得提早完工懲罰與延遲完工懲罰之總合為最低。 本研究證明所探討之問題能以多項式時間演算法(polynomial time algorithm)求解。

(*聯絡人 ： [email protected])

Keywords:

• scheduling
• unrelated parallel-machine
• rate-modifying activity
• earliness and tardiness
• common due-date

Keywords:

• 關鍵詞 ： 排程、 非相關平行機台、 維修、 提早完工與延遲完工、 共同交貨時間點

Acknowledgements

We thank the editor and two anonymous reviewers for their valuable comments and suggestions on an earlier version of the paper. This research was supported in part by the National Science Council of Taiwan, Republic of China, under grant numbers NSC 99-2221-E-150-034-MY2 and NSC 100-2221-E-252-002-MY2.

Notes

(*聯絡人 ： [email protected])