American Institute of Mathematical Sciences

April  2019, 15(2): 633-645. doi: 10.3934/jimo.2018062

Immediate schedule adjustment and semidefinite relaxation

 1 School of Mathematics and Physics, University of Science and Technology Beijing, 30 Xueyuan Road, Haidian District, Beijing 100083, China 2 Business School, Nankai University, 94 Weijin Road, Nankai District, Tianjin 300071, China

* Corresponding author: Su Zhang

Received  November 2017 Revised  January 2018 Published  April 2018

Fund Project: The first author is supported by National Natural Science Foundation of China No. 11101028,11271206, and the Fundamental Research Funds for the Central Universities. The third author is supported by National Natural Science Foundation of China No. 11401322.

This paper considers the problem of temporary shortage of some resources within a project execution period. Mathematical models for two different cases of this problem are established. Semidefinite relaxation technique is applied to get immediate solvent of these models. Relationship between the models and their semidefinite relaxations is studied, and some numerical experiments are implemented, which show that these mathematical models are reasonable and feasible for practice, and semidefinite relaxation can efficiently solve the problem.

Citation: Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062
References:

show all references

References:
Project Network Diagram in Example 1
Project Network Diagram in Example 2
Basic Notations
 Symbol Definition $Pred(i)$ set of direct predecessors of Activity $i$ $Succ(i)$ set of direct successors of Activity $i$ $d_i$ processing time (or duration) of Activity $i$ $s_i$ start time of Activity $i$ according to the existing schedule $f_i$ completion time of Activity $i$ according to the existing schedule $R_k$ amount of originally available units of renewable resource $k$ in unit time $r_{ik}$ usage of Activity $i$ of renewable resource $k$ in unit time $t_0$ start time of the temporary shortage of resources $T$ lasting time of the resources shortage $\Delta R_k$ amount of decrement of resource $k$ in unit time
 Symbol Definition $Pred(i)$ set of direct predecessors of Activity $i$ $Succ(i)$ set of direct successors of Activity $i$ $d_i$ processing time (or duration) of Activity $i$ $s_i$ start time of Activity $i$ according to the existing schedule $f_i$ completion time of Activity $i$ according to the existing schedule $R_k$ amount of originally available units of renewable resource $k$ in unit time $r_{ik}$ usage of Activity $i$ of renewable resource $k$ in unit time $t_0$ start time of the temporary shortage of resources $T$ lasting time of the resources shortage $\Delta R_k$ amount of decrement of resource $k$ in unit time
Comparing the 1/3-Method with the Rounding Method
 $\Delta R_k$ 1/3-Method Rounding Method SDR Opt.Val $t^*$ Opt.Val $t^*$ Delay Time $2$ 15 infeasible 15.0000 15 1 $5$ 15 15 15.0000 15 1 $8$ 18 infeasible 15.4583 18 4 $11$ 19 19 16.7083 19 5
 $\Delta R_k$ 1/3-Method Rounding Method SDR Opt.Val $t^*$ Opt.Val $t^*$ Delay Time $2$ 15 infeasible 15.0000 15 1 $5$ 15 15 15.0000 15 1 $8$ 18 infeasible 15.4583 18 4 $11$ 19 19 16.7083 19 5
 [1] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [2] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

2019 Impact Factor: 1.366