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 and 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-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.

show all references

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.

[1]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[2]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[3]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71
[4]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691
[5]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076
[6]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190
[7]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[8]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174
[9]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008
[10]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
[11]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124
[12]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044
[13]

Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066
[14]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148
[15]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[16]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088
[17]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[18]

Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132
[19]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial and Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
[20]

Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy