Unrelated parallel machine scheduling with machine processing cost

Abstract: In practical scheduling problems, some factors such as depreciation cost, green costs like the amount of energy consumption or carbon emission, other resources consumption, raw material cost, etc., are not explicitly related to the machine processing times. Most of these factors can be generally considered as machine costs. Considering the machine cost as another objective alongside the other classical time-driven decision objectives can be an attractive work in scheduling problems. However, this subject has not been discussed thoroughly in the literature for the case the machines have fixed processing costs. This paper investigates a general unrelated parallel machine scheduling problem with the machine processing cost. In this problem, it is assumed that processing a job on a machine incurs a particular cost in addition to processing time. The considered objectives are the makespan and the total cost, which are minimized simultaneously to obtain Pareto optimal solutions. The efficacy of the mathematical programming approach to solve the considered problem is evaluated rigorously in this paper. In this respect, a multiobjective solution procedure is proposed to generate a set of appropriate Pareto solutions for the decision-maker based on the mathematical programming approach. In this procedure, the ϵ-constraint method is first used to convert the bi-objective optimization problem into single-objective problems by transferring the makespan to the set of constraints. Then, the single-objective problems are solved using the CPLEX software. Moreover, some strategies are also used to reduce the solution time of the problem. At the end of the paper, comprehensive numerical experiments are conducted to evaluate the performance of the proposed multiobjective solution procedure. A vast range of problem sizes is selected for the test problems, up to 50 machines and 500 jobs. Furthermore, some rigorous analyses are performed to significantly restrict the patterns of generating processing time and cost parameters for the problem instances. The experimental results demonstrate the mathematical programming solution approach's efficacy in solving the problem. It is observed that even for large-scale problems, a diverse set of uniformly distributed Pareto solutions can be generated in a reasonable time with the gaps from the optimality less than 0.03 most of the time.

How to cite this paper

 Safarzadeh, H & Niaki, S. (2023). Unrelated parallel machine scheduling with machine processing cost.International Journal of Industrial Engineering Computations , 14(1), 33-48.

Refrences

Branke, J., Branke, J., Deb, K., Miettinen, K., & Slowiński, R. (Eds.). (2008). Multiobjective optimization: Interactive and evolutionary approaches (Vol. 5252). Springer Science & Business Media.
Che, A., Wu, X., Peng, J., & Yan, P. (2017). Energy-efficient bi-objective single-machine scheduling with power-down mechanism. Computers & Operations Research, 85, 172-183.
Coello, C. A. C., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems (Vol. 5, pp. 79-104). New York: Springer.
CPLEX 12.6.0 Manual, ILOG Reference of "Running out of memory troubleshooting" - Retrieved from .
Demir, Y., & İşleyen, S. K. (2013). Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling, 37(3), 977-988.
Ding, J. Y., Song, S., & Wu, C. (2016). Carbon-efficient scheduling of flow shops by multi-objective optimization. European Journal of Operational Research, 248(3), 758-771.
Dósa, G., & Tan, Z. (2010). New upper and lower bounds for online scheduling with machine cost. Discrete Optimization, 7(3), 125-135.
Ham, A. (2017). Flexible job shop scheduling problem for parallel batch processing machine with compatible job families. Applied Mathematical Modelling, 45, 551-562.
Hasani, A., & Hosseini, S. M. H. (2020). A bi-objective flexible flow shop scheduling problem with machine-dependent processing stages: Trade-off between production costs and energy consumption. Applied Mathematics and Computation, 386, 125533.
Heydar, M., Mardaneh, E., & Loxton, R. (2022). Approximate dynamic programming for an energy-efficient parallel machine scheduling problem. European Journal of Operational Research, 302(1), 363-380.
Ho, W. H., Chiu, Y. H., & Chen, Y. J. (2018). Multi-objective Pareto adaptive algorithm for capacitated lot-sizing problems in glass lens production. Applied Mathematical Modelling, 53, 731-738.
Ji, M., Wang, J. Y., & Lee, W. C. (2013). Minimizing resource consumption on uniform parallel machines with a bound on makespan. Computers & Operations Research, 40(12), 2970-2974.
Karhi, S., & Shabtay, D. (2018). Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties. International Journal of Production Research, 56(9), 3080-3096.
Karimi, S., Kwon, S., & Ning, F. (2021). Energy-aware production scheduling for additive manufacturing. Journal of Cleaner Production, 278, 123183.
Keha, A. B., Khowala, K., & Fowler, J. W. (2009). Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56(1), 357-367.
Kolahan, F., & Kayvanfar, V. (2009). A heuristic algorithm approach for scheduling of multi-criteria unrelated parallel machines. International Journal of Industrial and Manufacturing Engineering, 3(11), 1406-1409.
Kong, M., Pei, J., Liu, X., Lai, P. C., & Pardalos, P. M. (2020). Green manufacturing: Order acceptance and scheduling subject to the budgets of energy consumption and machine launch. Journal of Cleaner Production, 248, 119300.
Kononov, A. V., Kovalyov, M. Y., & Lin, B. M. (2019). Minimizing machine assignment costs over Δ-approximate solutions of the scheduling problem P|| Cmax. Theoretical Computer Science, 793, 70-78.
Ku, W. Y., & Beck, J. C. (2016). Mixed integer programming models for job shop scheduling: A computational analysis. Computers & Operations Research, 73, 165-173.
Lee, K., Leung, J. Y., Jia, Z. H., Li, W., Pinedo, M. L., & Lin, B. M. (2014). Fast approximation algorithms for bi-criteria scheduling with machine assignment costs. European Journal of Operational Research, 238(1), 54-64.
Leung, J. Y. T., Lee, K., & Pinedo, M. L. (2012). Bi-criteria scheduling with machine assignment costs. International Journal of Production Economics, 139(1), 321-329.
Li, K., Zhang, H. J., Cheng, B. Y., & Pardalos, P. M. (2018). Uniform parallel machine scheduling problems with fixed machine cost. Optimization Letters, 12(1), 73-86.
Li, K., Zhang, X., Leung, J. Y. T., & Yang, S. L. (2016). Parallel machine scheduling problems in green manufacturing industry. Journal of Manufacturing Systems, 38, 98-106.
Liang, P., Yang, H. D., Liu, G. S., & Guo, J. H. (2015). An ant optimization model for unrelated parallel machine scheduling with energy consumption and total tardiness. Mathematical Problems in Engineering, e907034.
Liu, Z., Lee, W. C., & Wang, J. Y. (2016). Resource consumption minimization with a constraint of maximum tardiness on parallel machines. Computers & Industrial Engineering, 97, 191-201.
Meng, L., Zhang, C., Shao, X., & Ren, Y. (2019). MILP models for energy-aware flexible job shop scheduling problem. Journal of Cleaner Production, 210, 710-723.
Mokhtari, H., & Hasani, A. (2017). An energy-efficient multi-objective optimization for flexible job-shop scheduling problem. Computers & Chemical Engineering, 104, 339-352.
Naderi, B., Gohari, S., & Yazdani, M. (2014). Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling, 38(24), 5767-5780.
Nasiri, M. M., Abdollahi, M., Rahbari, A., Salmanzadeh, N., & Salesi, S. (2018). Minimizing the energy consumption and the total weighted tardiness for the flexible flowshop using NSGA-II and NRGA. Journal of Industrial and Systems Engineering, 11(Special issue: 14th International Industrial Engineering Conference), 150-162.
Özgüven, C., Özbakır, L., & Yavuz, Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34(6), 1539-1548.
Pan, J. C. H., & Chen, J. S. (2005). Mixed binary integer programming formulations for the reentrant job shop scheduling problem. Computers & Operations Research, 32(5), 1197-1212.
Pan, R., Wang, Q., Li, Z., Cao, J., & Zhang, Y. (2022). Steelmaking-continuous casting scheduling problem with multi-position refining furnaces under time-of-use tariffs. Annals of Operations Research, 310(1), 119-151.
Pinedo, M.L. (2016). Scheduling: Theory, Algorithms, and Systems. 5th ed. 2016 edition. ed. Springer, New York.
Safarzadeh, H., & Niaki, S. T. A. (2019). Bi-objective green scheduling in uniform parallel machine environments. Journal of Cleaner Production, 217, 559-572.
Unlu, Y., & Mason, S. J. (2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering, 58(4), 785-800.
Wang, H., & Alidaee, B. (2018). Unrelated parallel machine selection and job scheduling with the objective of minimizing total workload and machine fixed costs. IEEE Transactions on Automation Science and Engineering, 15(4), 1955-1963.
Wang, S., Wang, X., Chu, F., & Yu, J. (2020). An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production. International Journal of Production Research, 58(8), 2283-2314.
Wei, Z., Liao, W., & Zhang, L. (2022). Hybrid energy-efficient scheduling measures for flexible job-shop problem with variable machining speeds. Expert Systems with Applications, 197, 116785.
Wu, X., & Che, A. (2019). A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 82, 155-165.
Xie, F., Xu, Z., Zhang, Y., & Bai, Q. (2015). Scheduling games on uniform machines with activation cost. Theoretical Computer Science, 580, 28-35.
Yeh, W. C., Chuang, M. C., & Lee, W. C. (2015). Uniform parallel machine scheduling with resource consumption constraint. Applied Mathematical Modelling, 39(8), 2131-2138.
Zeng, Y., Che, A., & Wu, X. (2018). Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering Optimization, 50(1), 19-36.
Zhang, L., Deng, Q., Gong, G., & Han, W. (2020). A new unrelated parallel machine scheduling problem with tool changes to minimise the total energy consumption. International Journal of Production Research, 58(22), 6826-6845.
Ziaee, M., & Sadjadi, S. J. (2007). Mixed binary integer programming formulations for the flow shop scheduling problems. A case study: ISD projects scheduling. Applied Mathematics and Computation, 185(1), 218-228.