Multi-agent heterogeneous parallel machines scheduling problem with energy cost and just-in-time jobs

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University

Abstract

In the classic models of scheduling problems, researchers mostly concentrate on the objectives considering jobs completion time. Due to the relation among economy, energy and environmental concerns, attention to the energy use of machines have been considered by researchers in the field of scheduling in recent years. Also, In the literature of scheduling problems, it is mostly assumed that one agent try to optimize the problem. But, occasionally there are several agents that each has their own jobs and they must use a series of common resources to process them. In this study, a two-agent heterogeneous parallel-machines scheduling problem is studied in which the process speed of each job on each machine is adjustable. Since there is a direct link between the energy used in machines and process speed, the used energy costs affect on scheduling problem. In this study, the first agent is tried to minimize total tardiness penalty as well as energy costs of production machines and the second agent is tried to minimize total tardiness and earliness. The suitable schedule should be considered to allocate and sequence jobs of agents to the common resources to optimize appropriately the agent’s objective functions. Since the proposed problem is Np-hard, in order to solve it in large scale problems, a Memetic algorithm is developed and to verify the performance of this algorithm, we take into comparison the results of Memetic algorithm with the results of GAMS software and of another meta-heuristic algorithm.

Keywords

References

[1] Pinedo, M., (2001). Scheduling: Theory, Algorithms, and Systems. Prentice-Hall Inc., Englewood Cliffs, N.J.
[2] Kim, D-W., Kim, K-H., Jang, W., Chen, F., (2002). “Unrelated parallel machine scheduling with setup times using simulated annealing”. Robotics and ComputerIntegrated Manufacturing, 18: 223-231.
[3] Vredeveld, T., Hurkens, C., (2002). “Experimental comparison of approximation algorithms for scheduling unrelated parallel machines”. Informs Journal on Computing, 14(2): 175-189.
[4] Rogendran, R., Subur, F., (2004). “Unrelated parallel machine scheduling with job splitting”. IIE Transaction, 36: 356-372.
[5] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., Sassani, F., (2009). “Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints”. Computers & Operations Research, 36: 3224-3230.
[6] Balin, S., (2011). “Non-identical parallel machine scheduling using genetic algorithm”. Expert System with Applications, 38: 6814-6821.
[7] Lin, Y. K., Pfund, M. E., Fowler, J. W., (2011). “Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problem”. Computers & Operations Research, 38(6): 901–916.
[8] Vallada, E., Ruiz, R., (2011). “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times”. European Journal of Operational Research, 211: 612-622.
[9] Rodriguez, F. J., Lozano, M., Blum, C., Garcia-Martinez, C., (2013). “An iterated greedy algorithm for the large-scale unrelated parallel machine scheduling problem”. Computers & Operations Research, 40: 1829-1841.
[10] Fanjul-Peyro, L., Perea, F., Ruiz, R., (2017). “Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources”. European Journal of Operational Research 000 (2017): 1-12.
[11] Hoogeveen, H., (2005). “Multicriteria scheduling”. European Journal of Operational Research, 167: 592e623.
[12] Liu, Y., Dong, H., Lohse, N., Petrovic, S., Gindy, N., (2013). “An investigation into minimizingtotal energy consumption and total weighted tardiness in job shops”.Journal of Cleaner Production, 1e10.
[13] Yan, H., Fei, L., Hua-jun, C., Cong-bo, L., (2005). A bi-objective model for job-shopscheduling problem to minimize both energy consumption and makespan.J. Cent. South Univ. Technol. 12.
[14] Liu, X., Zou, F., Zhang, X., (2008). “Mathematical model and genetic optimization forhybrid flow shop scheduling problem based on energy consumption”. In: 2008 Chinese Control and Decision Conference, pp. 1002e1007.
[15] Yildirim, M.B., Mouzon, G., (2011). “Single-machine sustainable production planning tominimize total energy consumption and total completion time using a multipleobjective genetic algorithm”. In: IEEE Transactions on Engineering Management,pp. 1e13.
[16] Fang, K., Uhan, N., Zhao, F., Sutherland, J.W., (2011). “A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction”. Journal of Manufacturing Systems, 30, 234e240.
[17] Fang, K., Bertrand M.T., Lin. (2012). “Parallel-machine scheduling to minimize tardiness penalty and power cost”. Computers & Industrial Engineering, 64 (2013): 224-234.
[18] Ada Che, Shibohua Zhang, Xueqi, Wu. (2017). “Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs”. Journal of cleaner production.156(10): 688-697.
[19] Moon, J.Y., Shin, K., Park, J., (2013). “Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency”. International Journal of Advanced Manufacturing Technology,68, 523-535.
[20] Ding, J.Y., Song, S., Zhang, R., Chiong, R., (2016). “Parallel machine scheduling under time-of-useelectricity prices: new models and optimization approaches”. IEEE Transactions on Automation Science & Engineering,13(2): 1138-1154.
[21] Luo, H., Du, B., Huang, G.Q., Chen, H., Li, X., (2013). “Hybrid flow shop scheduling considering machine electricity consumption cost”. International Journal of Production Economics,146: 423-439.
[22] Zhang, H., Zhao, F., Fang, K., Sutherland, J.W., (2014). “Energy-conscious flow shop scheduling under time-of-use electricity tariffs”. CIRP Annals – Manufacturing Technology,63: 37-40.
[23] Sharma, A., Zhao, F., Sutherland, J.W., (2015). “Econological scheduling of a manufacturingenterprise operating under a time-of-use electricity tariff”. Journal of Cleaner Production,108: 256-270.
[24] Baker, K. R., Smith, J. C. (2003). “A multiple-criterion model for machine scheduling”. Journal of Scheduling, 6(1): 7-16.
[25] Agnetis, A., Mirchandani, P. B., Pacciarelli, D., Pacifici, A., (2004). “Scheduling problems with two competing agents”. Operations Research, 52(2): 229-242.
[26] Cheng, T. C. E., Ng, C. T., Yuan, J. J., (2006). “Multi-agent scheduling on a singlemachine to minimize total weighted number of tardy jobs”. Theoretical Computer Science, 362(1–3): 273-281.
[27] Leung, J. Y. T., Pinedo, M., Wan, G. H., (2010). Competitive two agents scheduling and its applications. Operations Research, 58(2): 458-469.
[28] Wu, C. C., Huang, S. K., Lee, W. C., (2011). “Two-agent scheduling with learning consideration”. Computers & Industrial Engineering, 61(4): 1324-1335.
[29] Cheng, T. C. E., Cheng, S. R., Wu, W. H., Hsu, P. H., Wu, C. C., (2011). “A two-agent single machine scheduling problem with truncated sum-of-processing-timesbased learning considerations”. Computers & Industrial Engineering, 60(4): 534-541.
[30] Elvikis, D., Hamacher, H. W., T’kindt, V., (2011). “Scheduling two agents on uniformparallel machines with makespan and cost functions”. Journal of Scheduling, 14(5): 471-481.
[31] Lee, W. C., Chung, Y. H., Hu, M. C., (2012). “Genetic algorithms for a two-agentsingle-machine problem with release time”. Applied Soft Computing, 12(11):3580-3589.
[32] Lee, W. C., Wang, J. Y., Lin, M. C., (2016). “A branch-and-bound algorithm forminimizing the total weighted completion time on parallel identical machineswith two competing agents”. Knowledge-Based Systems, 105: 68-82.
[33] Lee, W. C., Wang, J. Y., (2014). “A scheduling problem with three competing agents”. Computers & Operations Research, 51: 208-217.
[34] Lee, W. C., Wang, J. Y., (2017). “A three-agent scheduling problem for minimizing the makespan on a single machine”. Computers & Industrial Engineering, 106: 147-160.
[35] Shiau, Y. R., Tsai, M. S., Lee, W. C., Cheng, T. C. E., (2015). “Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time”. Computers & Industrial Engineering, 87: 580-589.
[36] Yuan, J. J., Ng, C. T., Cheng, T. C. E., (2015). “Two-agent single-machine schedulingwith release dates and preemption to minimize the maximum lateness”. Journal of Scheduling, 18(2): 147-153.
[37] Pinedo, M. (2001). Scheduling: Theory, Algorithms, and Systems. Prentice-Hall Inc., Englewood Cliffs, N.J.
[38] Garey, MR., Johnson, DS., (1978). “Strong NP-completeness results: Motivation,examples, and implications”. Journal of the Association for Computing Machinery,25(3): 499-508.
[39] Behnamian J., Fatemi Ghomi SMT, Zandieh M., (2009). “A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic”. Expert Systems with Applications, 36(8): 11057-1106
Journal of Industrial Engineering Research in Production Systems
Volume 7, Issue 15
March 2020
Pages 287-303

Files

Share

How to cite

Statistics