Article Contents
Article Contents

# The inverse parallel machine scheduling problem with minimum total completion time

• 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.
Mathematics Subject Classification: 90B35, 90C27.

 Citation:

•  [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.