American Institute of Mathematical Sciences

Advanced
  • Previous Article
    LS-SVM approximate solution for affine nonlinear systems with partially unknown functions
  • JIMO Home
  • This Issue
  • Next Article
    A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents
April  2014, 10(2): 613-620. doi: 10.3934/jimo.2014.10.613

The inverse parallel machine scheduling problem with minimum total completion time

Hongtruong Pham 1, and  Xiwen Lu 1,

1. 

Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China

Received  July 2012 Revised  May 2013 Published  October 2013

In inverse scheduling problems, a job sequence is given and the objective is to determine the minimal perturbation to parameters, such as processing times or weights of jobs so that the given schedule becomes optimal with respect to a pre-selected objective function. In this paper we study the necessary and sufficient conditions for optimality of the total completion time problem on parallel machines and inverse scheduling problem of the total completion time objective on parallel machines in which the processing times are minimally adjusted, so that a given target job sequence becomes an optimal schedule.
Keywords: parallel machine., Scheduling, inverse, processing times.
Mathematics Subject Classification: 90B35, 90C2.
Citation: Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
References:
[1]

R. K. Ahuja and J. B. Orlin, Inverse optimization,, Operations Research, 49 (2001), 771.  doi: 10.1287/opre.49.5.771.10607.  Google Scholar

[2]

Mokhatar S. Bazaraa, Hanif D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms,, Third edition, (2006).  doi: 10.1002/0471787779.  Google Scholar

[3]

P. Brucker, Scheduling Algorithms,, Springer, (2001).   Google Scholar

[4]

P. Brucker and N. V. Shakhlevich, Inverse scheduling with maximum lateness objective,, Journal of Scheduling, 12 (2009), 475.  doi: 10.1007/s10951-009-0117-9.  Google Scholar

[5]

P. Brucker and N. V. Shakhlevich, Inverse Scheduling: Two-Machine Flow-Shop Problem,, Journal of Scheduling, (2009).  doi: 10.1007/s10951-010-0168-y.  Google Scholar

[6]

R. J. Chen, F. Chen and G. C. Tang, Inverse problems of a single machine scheduling to minimize the total completion time,, Journal of Shanghai Second Polytechnic University, 22 (2005), 1.   Google Scholar

[7]

D. Goldfar and A. Idnani, A numerically stable dual method for solving strictly convex quadratic program,, Mathematical Programming, 27 (1983), 1.  doi: 10.1007/BF02591962.  Google Scholar

[8]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results,, Journal of Combinatorial Optimization, 8 (2004), 329.  doi: 10.1023/B:JOCO.0000038914.26975.9b.  Google Scholar

[9]

Y. W. Jiang, L. C. Liu and W. Biao, Inverse minimum cost flow problems under the weighted Hamming distance,, European Journal of Operational Research, 207 (2010), 50.  doi: 10.1016/j.ejor.2010.03.029.  Google Scholar

[10]

C. Koulamas, Inverse scheduling with controllable job parameters,, International Journal of Services and Operations Management, 1 (2005), 35.  doi: 10.1504/IJSOM.2005.006316.  Google Scholar

[11]

L. C. Liu and J. Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance,, Journal of Combinatorial Optimization, 12 (2006), 395.  doi: 10.1007/s10878-006-9006-8.  Google Scholar

[12]

L. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance,, Journal of Global Optimization, 43 (2009), 83.  doi: 10.1007/s10898-008-9294-x.  Google Scholar

[13]

X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems,, Journal of Industrial and Management Optimization, 5 (2009), 319.  doi: 10.3934/jimo.2009.5.319.  Google Scholar

[14]

C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems,, Optimization, 40 (1997), 147.  doi: 10.1080/02331939708844306.  Google Scholar

[15]

X. G. Yang and J. Z. Zhang, Some inverse min-max network problems under weighted $l_1$ and $l_\infty$ norms with bound constraints on changes,, Journal of Combinatorial Optimization, 13 (2007), 123.  doi: 10.1007/s10878-006-9016-6.  Google Scholar

[16]

X. Yang and J. Zhang, Some new results on inverse sorting problems,, Lecture Notes in Computer Science, 3595 (2005), 985.  doi: 10.1007/11533719_99.  Google Scholar

[17]

F. Zhang, T. C. Ng and G. C. Tang, Inverse scheduling: Applications in shipping,, International Journal of Shipping and Transport Logistics, 3 (2011), 312.  doi: 10.1504/IJSTL.2011.040800.  Google Scholar

[18]

J. Z. Zhang and Z. H. Liu, A further study on inverse linear programming problems,, Journal of Computational and Applied Mathematics, 106 (1999), 345.  doi: 10.1016/S0377-0427(99)00080-1.  Google Scholar

show all references

References:
[1]

R. K. Ahuja and J. B. Orlin, Inverse optimization,, Operations Research, 49 (2001), 771.  doi: 10.1287/opre.49.5.771.10607.  Google Scholar

[2]

Mokhatar S. Bazaraa, Hanif D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms,, Third edition, (2006).  doi: 10.1002/0471787779.  Google Scholar

[3]

P. Brucker, Scheduling Algorithms,, Springer, (2001).   Google Scholar

[4]

P. Brucker and N. V. Shakhlevich, Inverse scheduling with maximum lateness objective,, Journal of Scheduling, 12 (2009), 475.  doi: 10.1007/s10951-009-0117-9.  Google Scholar

[5]

P. Brucker and N. V. Shakhlevich, Inverse Scheduling: Two-Machine Flow-Shop Problem,, Journal of Scheduling, (2009).  doi: 10.1007/s10951-010-0168-y.  Google Scholar

[6]

R. J. Chen, F. Chen and G. C. Tang, Inverse problems of a single machine scheduling to minimize the total completion time,, Journal of Shanghai Second Polytechnic University, 22 (2005), 1.   Google Scholar

[7]

D. Goldfar and A. Idnani, A numerically stable dual method for solving strictly convex quadratic program,, Mathematical Programming, 27 (1983), 1.  doi: 10.1007/BF02591962.  Google Scholar

[8]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results,, Journal of Combinatorial Optimization, 8 (2004), 329.  doi: 10.1023/B:JOCO.0000038914.26975.9b.  Google Scholar

[9]

Y. W. Jiang, L. C. Liu and W. Biao, Inverse minimum cost flow problems under the weighted Hamming distance,, European Journal of Operational Research, 207 (2010), 50.  doi: 10.1016/j.ejor.2010.03.029.  Google Scholar

[10]

C. Koulamas, Inverse scheduling with controllable job parameters,, International Journal of Services and Operations Management, 1 (2005), 35.  doi: 10.1504/IJSOM.2005.006316.  Google Scholar

[11]

L. C. Liu and J. Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance,, Journal of Combinatorial Optimization, 12 (2006), 395.  doi: 10.1007/s10878-006-9006-8.  Google Scholar

[12]

L. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance,, Journal of Global Optimization, 43 (2009), 83.  doi: 10.1007/s10898-008-9294-x.  Google Scholar

[13]

X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems,, Journal of Industrial and Management Optimization, 5 (2009), 319.  doi: 10.3934/jimo.2009.5.319.  Google Scholar

[14]

C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems,, Optimization, 40 (1997), 147.  doi: 10.1080/02331939708844306.  Google Scholar

[15]

X. G. Yang and J. Z. Zhang, Some inverse min-max network problems under weighted $l_1$ and $l_\infty$ norms with bound constraints on changes,, Journal of Combinatorial Optimization, 13 (2007), 123.  doi: 10.1007/s10878-006-9016-6.  Google Scholar

[16]

X. Yang and J. Zhang, Some new results on inverse sorting problems,, Lecture Notes in Computer Science, 3595 (2005), 985.  doi: 10.1007/11533719_99.  Google Scholar

[17]

F. Zhang, T. C. Ng and G. C. Tang, Inverse scheduling: Applications in shipping,, International Journal of Shipping and Transport Logistics, 3 (2011), 312.  doi: 10.1504/IJSTL.2011.040800.  Google Scholar

[18]

J. Z. Zhang and Z. H. Liu, A further study on inverse linear programming problems,, Journal of Computational and Applied Mathematics, 106 (1999), 345.  doi: 10.1016/S0377-0427(99)00080-1.  Google Scholar

[1]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018
[2]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[3]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[4]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072
[5]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[6]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[7]

Noriyoshi Fukaya. Uniqueness and nondegeneracy of ground states for nonlinear Schrödinger equations with attractive inverse-power potential. Communications on Pure & Applied Analysis, 2021, 20 (1) : 121-143. doi: 10.3934/cpaa.2020260
[8]

Kai Yang. Scattering of the focusing energy-critical NLS with inverse square potential in the radial case. Communications on Pure & Applied Analysis, 2021, 20 (1) : 77-99. doi: 10.3934/cpaa.2020258

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (50)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences