Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (4): 83-91.
• Original Articles • Previous Articles Next Articles
ZHONG Xue-Ling, WANG Guo-Qing, CHENG Ming-Bao, LI Xiao-Chun
Online:
Published:
Abstract: This paper discusses the problem that $n$ jobs with their own deadlines and precedence constraints have to be processed on a single machine considering the idle insert. The objective is to find a preemptive job sequence and determine jobs' starting times so as to minimize the maximum earliness cost. Firstly, we consider two special cases: (1) common deadline and precedence constraints; (2) arbitrary deadlines and no precedence constraint. The $O(n^2)$ algorithms are provided respectively. Then the general case of arbitrary deadlines and precedence constraints is considered based on the two special cases, and an $O(n^2)$ algorithm is developed too. Since tardy jobs are prohibited, it's possible that there is no feasible sequence for the problem. We consider the feasibility primarily.
ZHONG Xue-Ling, WANG Guo-Qing, CHENG Ming-Bao, LI Xiao-Chun. Preemptive Scheduling to Minimize Maximum Earliness Cost[J]. Operations Research Transactions, 2010, 14(4): 83-91.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/
https://www.ort.shu.edu.cn/EN/Y2010/V14/I4/83