• Previous Article
    Note on : Supply chain inventory model for deteriorating items with maximum lifetime and partial trade credit to credit risk customers
  • JIMO Home
  • This Issue
  • Next Article
    An adaptive probabilistic algorithm for online k-center clustering
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, doi: 10.3934/jimo.2018062
References:
[1]

M. BartuschR. H. Mohring and F. J. Randermacher, Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16 (1988), 201-240.

[2]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, MOS-SIAM Series on Optimization, 2001.

[3]

J. BlazewiczJ. K. Lenstra and A. H. G. Kan Rinnooy, Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5 (1983), 11-24. doi: 10.1016/0166-218X(83)90012-4.

[4]

S. Boyd and L. Vandenberghe, Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization, Communications, Computation, Control, and Signal Processing, Springer, 1997,279-287 doi: 10.1007/978-1-4615-6281-8_15.

[5]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, first edition, 2004.

[6]

P. Brucker, Scheduling and constraint propagation, Discrete Applied Mathematics, 123 (2002), 227-256. doi: 10.1016/S0166-218X(01)00342-0.

[7]

M. Goemans and D. Williamson, Imporved approximation algorihtms for maximum cut and satisfiablity problems using semidefinite programming, J. Assoc. Comput. Mach., 42 (1995), 1115-1145. doi: 10.1145/227683.227684.

[8]

S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207 (2010), 1-14. doi: 10.1016/j.ejor.2009.11.005.

[9]

D. Henrion, J. Lasserre and J. Loefberg, GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779, http://homepages.laas.fr/henrion/software/gloptipoly3. doi: 10.1080/10556780802699201.

[10]

H. Li and N. K. Womer, Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming, European Journal of Operational Research, 246 (2015), 20-33. doi: 10.1016/j.ejor.2015.04.015.

[11]

U. MalikI. M. JaimoukhaG. D. Halikias and S. K. Gungah, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Math. Program., 107 (2006), 505-515. doi: 10.1007/s10107-005-0692-2.

[12]

I. Pólik, Addendum to the SeDuMi user guide version 1.1, http://sedumi.ie.lehigh.edu/?page_id=58, 2005.

[13]

A. A. B. PritskerL. J. Watters and P. M. Wolfe, Multiproject scheduling with limited resources: A zero-one programming approach, Management Science, 16 (1969), 93-108. doi: 10.1287/mnsc.16.1.93.

[14]

F. Rendl, Semidefinite relaxations for integer programming, 50 Years of Integer Programming 1958-2008, (2009), 687-726. doi: 10.1007/978-3-540-68279-0_18.

[15]

N. Z. Shor, Quadratic optimization problems, Soviet. J. Comput. Systems Sci., 25 (1987), 1-11.

[16]

J. F. Sturm, Using SeDuMi 1.02, a matlab toolbox for optimizativer over smmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.

[17]

X. Sun and R. Li, New progress in integer programming, Operations Research Transactions, 18 (2014), 39-67.

[18]

L. Vandenerghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.

[19]

H. WakiS. KimM. Kojima and M. Muramatsu, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM Journal on Optimization, 17 (2006), 218-242. doi: 10.1137/050623802.

[20]

H. Wolkowicz, R. Saigak and L. Vandenerghe, Handbook of Semidefinite Programming, Kluwer's Publisher, 2000.

[21]

F. Zhang, The Schur Complement and Its Applications: Numerical Methods and Algorithms, Springer Science Business Media, 2005.

[22]

X. ZhengX. SunD. Li and Y. Xia, Duality gap estimation of linear equality constraintd binary quadratic programming, Mathematics of Operations Research, 35 (2010), 864-880. doi: 10.1287/moor.1100.0472.

show all references

References:
[1]

M. BartuschR. H. Mohring and F. J. Randermacher, Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16 (1988), 201-240.

[2]

A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, MOS-SIAM Series on Optimization, 2001.

[3]

J. BlazewiczJ. K. Lenstra and A. H. G. Kan Rinnooy, Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5 (1983), 11-24. doi: 10.1016/0166-218X(83)90012-4.

[4]

S. Boyd and L. Vandenberghe, Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization, Communications, Computation, Control, and Signal Processing, Springer, 1997,279-287 doi: 10.1007/978-1-4615-6281-8_15.

[5]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, first edition, 2004.

[6]

P. Brucker, Scheduling and constraint propagation, Discrete Applied Mathematics, 123 (2002), 227-256. doi: 10.1016/S0166-218X(01)00342-0.

[7]

M. Goemans and D. Williamson, Imporved approximation algorihtms for maximum cut and satisfiablity problems using semidefinite programming, J. Assoc. Comput. Mach., 42 (1995), 1115-1145. doi: 10.1145/227683.227684.

[8]

S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207 (2010), 1-14. doi: 10.1016/j.ejor.2009.11.005.

[9]

D. Henrion, J. Lasserre and J. Loefberg, GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), 761-779, http://homepages.laas.fr/henrion/software/gloptipoly3. doi: 10.1080/10556780802699201.

[10]

H. Li and N. K. Womer, Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming, European Journal of Operational Research, 246 (2015), 20-33. doi: 10.1016/j.ejor.2015.04.015.

[11]

U. MalikI. M. JaimoukhaG. D. Halikias and S. K. Gungah, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Math. Program., 107 (2006), 505-515. doi: 10.1007/s10107-005-0692-2.

[12]

I. Pólik, Addendum to the SeDuMi user guide version 1.1, http://sedumi.ie.lehigh.edu/?page_id=58, 2005.

[13]

A. A. B. PritskerL. J. Watters and P. M. Wolfe, Multiproject scheduling with limited resources: A zero-one programming approach, Management Science, 16 (1969), 93-108. doi: 10.1287/mnsc.16.1.93.

[14]

F. Rendl, Semidefinite relaxations for integer programming, 50 Years of Integer Programming 1958-2008, (2009), 687-726. doi: 10.1007/978-3-540-68279-0_18.

[15]

N. Z. Shor, Quadratic optimization problems, Soviet. J. Comput. Systems Sci., 25 (1987), 1-11.

[16]

J. F. Sturm, Using SeDuMi 1.02, a matlab toolbox for optimizativer over smmetric cones, Optim. Methods Softw., 11/12 (1999), 625-653.

[17]

X. Sun and R. Li, New progress in integer programming, Operations Research Transactions, 18 (2014), 39-67.

[18]

L. Vandenerghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.

[19]

H. WakiS. KimM. Kojima and M. Muramatsu, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM Journal on Optimization, 17 (2006), 218-242. doi: 10.1137/050623802.

[20]

H. Wolkowicz, R. Saigak and L. Vandenerghe, Handbook of Semidefinite Programming, Kluwer's Publisher, 2000.

[21]

F. Zhang, The Schur Complement and Its Applications: Numerical Methods and Algorithms, Springer Science Business Media, 2005.

[22]

X. ZhengX. SunD. Li and Y. Xia, Duality gap estimation of linear equality constraintd binary quadratic programming, Mathematics of Operations Research, 35 (2010), 864-880. doi: 10.1287/moor.1100.0472.

Figure 1.  Project Network Diagram in Example 1
Figure 2.  Project Network Diagram in Example 2
Table 1.  Basic Notations
SymbolDefinition
$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
SymbolDefinition
$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
Table 2.  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]

Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial & Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565

[2]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[3]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-16. doi: 10.3934/jimo.2018076

[4]

Helene Frankowska, Elsa M. Marchini, Marco Mazzola. A relaxation result for state constrained inclusions in infinite dimension. Mathematical Control & Related Fields, 2016, 6 (1) : 113-141. doi: 10.3934/mcrf.2016.6.113

[5]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[6]

Ciro D'Apice, Peter I. Kogut, Rosanna Manzo. On relaxation of state constrained optimal control problem for a PDE-ODE model of supply chains. Networks & Heterogeneous Media, 2014, 9 (3) : 501-518. doi: 10.3934/nhm.2014.9.501

[7]

Franz Wirl, Andreas J. Novak. Instability and growth due to adjustment costs. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 63-76. doi: 10.3934/naco.2013.3.63

[8]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[9]

Xuepeng Zhang, Zhibin Liang. Optimal layer reinsurance on the maximization of the adjustment coefficient. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 21-34. doi: 10.3934/naco.2016.6.21

[10]

Chrystie Burr, Laura Gardini, Ferenc Szidarovszky. Discrete time dynamic oligopolies with adjustment constraints. Journal of Dynamics & Games, 2015, 2 (1) : 65-87. doi: 10.3934/jdg.2015.2.65

[11]

Dequan Yue, Wuyi Yue. A heterogeneous two-server network system with balking and a Bernoulli vacation schedule. Journal of Industrial & Management Optimization, 2010, 6 (3) : 501-516. doi: 10.3934/jimo.2010.6.501

[12]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

[13]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

[14]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[15]

Constantine M. Dafermos. Hyperbolic balance laws with relaxation. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4271-4285. doi: 10.3934/dcds.2016.36.4271

[16]

Nahla Abdellatif, Radhouane Fekih-Salem, Tewfik Sari. Competition for a single resource and coexistence of several species in the chemostat. Mathematical Biosciences & Engineering, 2016, 13 (4) : 631-652. doi: 10.3934/mbe.2016012

[17]

Robert Stephen Cantrell, Chris Cosner, Shigui Ruan. Intraspecific interference and consumer-resource dynamics. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 527-546. doi: 10.3934/dcdsb.2004.4.527

[18]

Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63

[19]

Evans K. Afenya. Using Mathematical Modeling as a Resource in Clinical Trials. Mathematical Biosciences & Engineering, 2005, 2 (3) : 421-436. doi: 10.3934/mbe.2005.2.421

[20]

Irina Kareva, Faina Berezovkaya, Georgy Karev. Mixed strategies and natural selection in resource allocation. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1561-1586. doi: 10.3934/mbe.2013.10.1561

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (22)
  • HTML views (352)
  • Cited by (0)

Other articles
by authors

[Back to Top]