The inverse parallel machine scheduling problem with minimum total completion time

Hongtruong Pham; Xiwen Lu

doi:10.3934/jimo.2014.10.613

Article Contents

2014, Volume 10, Issue 2: 613-620. Doi: 10.3934/jimo.2014.10.613

This issue Previous Article A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents Next Article LS-SVM approximate solution for affine nonlinear systems with partially unknown functions

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

Received: June 30, 2012

Revised: April 30, 2013

Published: March 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 90B35, 90C27.

Citation:

Related Papers

Cited by

References

[1]	R. K. Ahuja and J. B. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783.doi: 10.1287/opre.49.5.771.10607.
[2]	Mokhatar S. Bazaraa, Hanif D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Third edition, Wiley-Interscience [John Wiley $&$ Sons], Hoboken, NJ, 2006.doi: 10.1002/0471787779.
[3]	P. Brucker, Scheduling Algorithms, Springer, Berlin, 2001.
[4]	P. Brucker and N. V. Shakhlevich, Inverse scheduling with maximum lateness objective, Journal of Scheduling, 12 (2009), 475-488.doi: 10.1007/s10951-009-0117-9.
[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.
[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-7.
[7]	D. Goldfar and A. Idnani, A numerically stable dual method for solving strictly convex quadratic program, Mathematical Programming, 27 (1983), 1-33.doi: 10.1007/BF02591962.
[8]	C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361.doi: 10.1023/B:JOCO.0000038914.26975.9b.
[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-54.doi: 10.1016/j.ejor.2010.03.029.
[10]	C. Koulamas, Inverse scheduling with controllable job parameters, International Journal of Services and Operations Management, 1 (2005), 35-43.doi: 10.1504/IJSOM.2005.006316.
[11]	L. C. Liu and J. Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12 (2006), 395-408.doi: 10.1007/s10878-006-9006-8.
[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-95.doi: 10.1007/s10898-008-9294-x.
[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-339.doi: 10.3934/jimo.2009.5.319.
[14]	C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems, Optimization, 40 (1997), 147-170.doi: 10.1080/02331939708844306.
[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-135.doi: 10.1007/s10878-006-9016-6.
[16]	X. Yang and J. Zhang, Some new results on inverse sorting problems, Lecture Notes in Computer Science, 3595 (2005), 985-992.doi: 10.1007/11533719_99.
[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-322.doi: 10.1504/IJSTL.2011.040800.
[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-359.doi: 10.1016/S0377-0427(99)00080-1.