Theoretical Analysis of Workload Imbalance Minimization Problem on Identical Parallel Machines

详细信息    查看全文

• 关键词：Parallel machines ; Workload balancing ; Normalized sum of square for workload deviations ; Mean absolute error
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9622
• 期：1
• 页码：296-303
• 全文大小：591 KB
• 参考文献：1.Al-Saleh, M.F., Yousif, A.E.: Properties of the standard deviation that are rarely mentioned in classrooms. Austrian J. Stat. 38(3), 193–202 (2009)
  2.Cossari, A., Ho, J.C., Paletta, G., Ruiz-Torres, A.J.: Minimizing workload balancing criteria on identical parallel machines. J. Ind. Prod. Eng. 30(3), 160–172 (2013)MATH
  3.Cossari, A., Ho, J.C., Paletta, G., Ruiz-Torres, A.J.: A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria. Comput. Oper. Res. 39(7), 1382–1393 (2012)MathSciNet CrossRef MATH
  4.Heinrich, K.: A heuristic algorithm for the loading problem in flexible manufacturing systems. Int. J. Flex. Manuf. Syst. 7, 229–254 (1995)CrossRef
  5.Ho, J.C., Tseng, T.L., Ruiz-Torres, A.J., López, F.J.: Minimizing the normalized sum of square for workload deviations on m parallel processors. Comput. Indus. Eng. 56(1), 186–192 (2009)CrossRef
  6.Keskinturk, T., Yildirim, M.B., Barut, M.: An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times. Comput. Oper. Res. 39(6), 1225–1235 (2012)MathSciNet CrossRef MATH
  7.Liu, M., Wu, C.: A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines. Artif. Intell. Eng. 13(4), 399–403 (1999)CrossRef
  8.Ouazene, Y., Hnaien, F., Yalaoui, F., Amodeo, L.: The joint load balancing and parallel machine scheduling problem. In: Bo, H., Morasch, K., Pickl, S., Siegle, M. (eds.) Operations Research Proceedings 2010. Operations Research Proceedings, pp. 497–502. Springer, Heidelberg (2011)CrossRef
  9.Ouazene, Y., Yalaoui, F., Chehade, H., Yalaoui, A.: Workload balancing in identical parallel machine scheduling using a mathematical programming method. Int. J. Comput. Intell. Syst. 7(sup1), 58–67 (2014)CrossRef
  10.Raghavendra, B.V., Murthy, A.N.N.: Some solution approaches to reduce the imbalance of workload in parallel machines while planning in flexible manufacturing system. Int. J. Eng. Sci. Technol. 2(5), 724–730 (2010)
  11.Raghavendra, B.V., Murthy, A.N.N.: Workload balancing in identical parallel machine scheduling while planning in flexible manufacturing system using genetic algorithm. ARPN J. Eng. Appl. Sci. 6(1), 49–55 (2011)
  12.Raghavendra, B.V., Murthy, A.N.N.: Some solution approaches to reduce the imbalance of workload in parallel machines while planning in flexible manufacturing system through genetic algorithm. Int. J. Eng. Sci. Technol. 2(5), 724–730 (2010)
  13.Rajakumar, S., Arunachalam, V.P., Selladurai, V.: Workflow balancing strategies in parallel machine scheduling. Int. J. Adv. Manufact. 23, 366–374 (2004)CrossRef
  14.Rajakumar, S., Arunachalam, V.P., Selladurai, V.: Workflow balancing in parallel machines through genetic algorithm. Int. J. Adv. Manuf. Technol. 33, 1212–1221 (2007)CrossRef
  15.Yildirim, M.B., Duman, E., Krishna, K., Senniappan, K.: Parallel machine scheduling with load balancing and sequence dependent setups. Int. J. Oper. Res. 4(1), 42–49 (2007)MathSciNet MATH
  
• 作者单位：Yassine Ouazene (17)
  Farouk Yalaoui (17)
  Alice Yalaoui (17)
  Hicham Chehade (18)
  
  17. Institut Charles Delaunay, Laboratoire d’Optimisation des Systèmes Industriels (UMR-CNRS 6281), Université de Technologie de Troyes, 12 rue Marie Curie, CS 42060, 10004, Troyes, France
  18. Opta-Lp, 2 Rue Gustave Eiffel, 10430, Rosières-prés-Troyes, France
  
• 丛书名：Intelligent Information and Database Systems
• ISBN：978-3-662-49390-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

This paper considers the problem of assigning N non-preemptive jobs to M identical parallel machines or processors as equally as possible. This problem is known as workload imbalance minimization problem. First, we establish that this problem can be formulated as the difference between the maximum and minimum workloads. In other words, it is defined as the minimization of the difference between the workload of the bottleneck machine and the workload of the fastest machine.