In this paper, the relocation scheduling problem with precedence constraints is investigated, where objective function is total weighted completion time. A polynomial algorithm is proposed for this kind of NP-hard scheduling problems based on the properties of relocation constraints and greedy rule. Also, it is proved that the performance ratio of the algorithm is 2 when each of chains is not nonpreemptive, and has the same jobs with the same processing times.
. MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS[J]. Mathematica Numerica Sinica, 2017, 39(4): 421-430.
Mohammad Ranjbar, Saeed Hosseinabadi, Foroogh Abasian. Minimizing total weighted late work in the resource-constrained project scheduling problem[J]. Applied Mathematical Modelling, 2013, 37:9776-9785.
Haitao Li, Norman K. Womer. Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming[J]. European Journal of Operational Research, 2015, 246:20-33.
Dvir Shabtay, George Steiner, Rui Zhang. Optimal coordination of resource allocation, due date assignment and scheduling decisions[J]. Omega, 2016, 65:41-54.
Kaplan E H. Relocation models for public housing redevelopment programs[J]. Environment and Planning B:Planning and Design, 1986, 13:5-19.
Kaplan E H, Amir A. A fast feasibility test for relocation problems[J]. European Journal of Operational Research, 1988, 35:201-206.
Kaplan E H, Berman O. OR hits the heights:Relocation planning at the orient heights housing project[J]. Interfaces, 1988, 18:14-22.
Amir A, Kaplan, E H. Relocation problems are hard. International Journal of Computer Mathematics, 1988, 25:101-110.
Xie J X. Polynomial algorithms for single machine shceduling problems with financial constraints[J]. Operations Research Letters, 1997, 21:39-42.
Kononov A V, Lin B M T. On relocation problems with multiple identical working crews[J]. Discrete Optimization, 2006, 3:366-381.
Kononov A V, Lin B M T. Minimizing the total weighted completion time in the relocation problem. Journal of Scheduling, 2010, 13:123-129.
Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling:Existing approaches and new results[J]. Artificial Intelligence, 2003, 143:151-188.
Neumann K, Schwindt C. Project scheduling with inventory constraints[J]. Mathematical Methods of Operations Research, 2002, 56:513-533.
Lin B M T, Hwang F J, Kononov A V. Relocation scheduling subject to finxed processing sequences[J]. Journal of Scheduling, 2016, 19:153-163.
Martin Skutella. A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective[J]. Operations Research Letters, 2016, 44:676-679.
Wang Ji-Bo, Wang Jian-Jun. Single-machine scheduling problems with precedence constraints and simple linear deterioration[J]. Applied Mathematical Modelling, 2015, 34:1172-1182.
Yuan Junling, Li Wenhua, Yuan Jinjiang. A best possible online algorithm for scheduling equallength jobs on two machines with chain precedence constraints[J]. Theoretical Computer Science,2012, 457:174-180.