Single-machine scheduling with decreasing time-dependent processing times to minimize total absolute differences in waiting times

Abstract

In this article we consider a single-machine scheduling problem with decreasing time-dependent job-processing times. Decreasing time-dependent job-processing times means that its processing time is a non-increasing function of its execution start time. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in the descending order of their normal processing times if they are placed before the job with the smallest normal processing time, but in the ascending order of their normal processing times if placed after it. We prove several other properties of an optimal schedule, and introduce two heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.

本研究考慮加工時間隨開工時間遞減的單機排程問題。 加工時間隨開工時間遞減意味著工件的加工時間是其開工時間的一個非增函數。 目標是找到一個排程使等待時間的總絕對差最小。 我們證明瞭最優排程具有V 型性質: 最小正常加工時間之前的工件按正常加工時間遞減排列 ， 最小正常加工時間之後的工件按正常加工時間遞增排列。 我們證明瞭最優排程具有其他幾個性質 ， 提出了兩個啟發式演算法 ， 並同下界進行了比較。 我們也給出了計算結果來評價啟發式演算法。

(*聯絡人： [email protected])

Keywords:

• scheduling
• single-machine
• time-dependent processing times
• total absolute differences in waiting times

Keywords:

• 關鍵字 ： 排程 ； 單機 ； 和開工時間有關的加工時間 ； 等待時間總絕對差

Acknowledgements

The authors are grateful for the editor and an anonymous referee for their helpful comments on earlier version of the article. This research was supported by the National Natural Science Foundation of China (Grant No. 11001181), The Hong Kong Polytechnic University (PolyU's project G-YL27) and the Program for Liaoning Excellent Talents in University (Grant No. LJQ2011014).

Notes

(*聯絡人： [email protected])