Resource Optimization in Job-shop Scheduling using Ant-Colony-Optimization Metaheuristic
ACO Algorithm to Resolve Scheduling Problem
Keywords:
Ant-colony-optimization, heuristic, job-shop, scheduling problem, makespan, aviation, helicopterAbstract
Present study elucidates the probity of ant colony optimization metaheuristic in minimizing the makespan by efficiently allocating jobs to workstations in general aviation maintenance. The metaheuristic technique is applied to real workplace problems in general aviation sector of Pakistan to resolve scheduling quandaries of XT-10 helicopters inspection in Burq Air Services (Pseudo names of organization and helicopter to keep anonymity). Secondary data for processing times of jobs at workstations was obtained from job cards and process sheets. Matlab codes were developed for reaching the optimal scheduling. Results indicated almost 25% improvement in efficiency, and proffered a customized yet efficient solution to scheduling problem in real aviation maintenance setup. The study posited that with the slight adjustment, the present model could be applied to other variants of job-shop, service industry, and similar areas of social sciences.
References
Abdullah, S., H. Turabieh, B. McCollum, & P. McMullan. A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics 18: 1-23 (2012).
Abel, R. Man is the Measure: A Cordial Invitation to the Central Problems in Philosophy. The Free Press, NY, USA (1976).
Adnan, M.A., M.A. Razzaque, I. Ahmed, & I.F. Isnin. Bio-Mimic Optimization Strategies in Wireless Sensor Networks: A Survey. Sensors 14: 299-345 (2013).
Aftab, M.T., M. Umer, & R. Ahmad. Jobs Scheduling and Worker Assignment Problem to Minimize Makespan using Ant Colony Optimization Metaheuristic. World Academy of Sciences, Engineering and Technology 6: 12-29 (2012).
Alzaqebah, M., & S. Abdullah. An adaptive artificial bee colony and late-acceptance hill-climbing algorithm for examination timetabling. Journal of Scheduling 17(3): 249-262 (2014).
Barbulescu, L., J.P. Watson, L.D. Whitley, & A.E. Howe. Scheduling space–ground communications for the air force satellite control network. Journal of Scheduling 7(1): 7-34 (2004).
Bianco, L., P. Dell’Olmo, & S. Giordani. Scheduling models for air traffic control in terminal areas. Journal of Scheduling 9(3): 223-253 (2006).
Blazewich, J., W. Domschke, & E. Pesch. The jobshop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research 93: 1-33 (1996).
Blum, C., & A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35 (3): 268-308 (2003).
Chelouah, R., & C. Baron. Ant colony algorithm hybridized with tabu and greedy searches as applied to multi-objective optimization in project management. Journal of Heuristics 13(6): 640-650 (2007).
Dorigo, M. Optimization Learning and Natural Algorithms. PhD Thesis,Politecnico di Milano, Italy (1992).
Dorigo, M., & T. Stutzle. Ant Colony Optimization. MIT Press: Cambridge, MA, USA (2004).
Ghiani, G., D. Laganà,G. Laporte, & F. Mari. Ant colony optimization for the arc routing problem with intermediate facilities under capacity and length restrictions. Journal of heuristics 16(2): 211- 233 (2010).
Gloag, E.S., M.A. Javed, H. Wang, & M. L. Gee. Stigmergy: A key driver of self-organization in bacterial biofilms. Communicative &Integrative Biology 6 (6): 11541-11546 (2013).
Global Optimum. (n.d.). Wikipedia: http://en.wikipedia.org/wiki/Global_optimum (Accessed on March 10, 2015).
Grandinetti, L., F. Guerriero ,L.D. Pugliese,& M. Sheikhalishahi. Heuristics for the local grid scheduling problem with processing time constraints. Journal of Heuristics 21(4): 523-547 (2015).
Groover, M.P. Fundamentals of Modern Manufacturing: Materials, Processes, and Systems.John Wiley & Sons (2007).
Hu, P.C. Minimizing total flow time for the worker assignment scheduling problem in the identical parallel-machine models. The International Journal of Advanced Manufacturing Technology 25 (9-10): 1046-1052 (2005).
Huang, R. H., C.L. Yang, & W.C. Cheng. Flexible job shop scheduling with due window- a two pheromone ant colony approach. International Journal of Production Economics 141 (2): 685-697 (2013).
Jair, C.D. Paternina-Arboleda,V. Cantillo, & J.R. Montoya-Torres. A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products. Journal of Heuristics 19(2): 233- 252 (2013).
Jing, T., & M. Tomohiro. Multi-objective flexible job shop scheduling with uncertain processing time and machine available constraint based on hybrid optimization approach. In: Automation and Logistics (ICAL), 2010 IEEE International Conference on Automation and Logisticsp. 581-586. IEEE (2010).
Kim, Y.D., B.J. Joo, & J.H. Shin. Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint. Journal of Heuristics 15(1): 19-42 (2009).
Liang, Y.C., Z.H. Lee, & Y. S. Chen. A novel ant colony optimization approach for on-line scheduling and due date determination. Journal of Heuristics 18(4): 571-591 (2012).
Lin, S.W., S.Y. Chou, & S. C. Chen. Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date. Journal of Heuristics 13(2): 151-165 (2007).
Mauguière, P., J.C. Billaut, & J.L. Bouquard. New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling 8(3): 211-231 (2005).
Mehmood, N., M. Umar, & R. Ahmad. A survey of recent developments for JSSP and FJSSP using ACO. Advanced Materials Research 816: 1133-1139 (2013).
Monteiro, M.S., D.B. Fontes, & F.A. Fontes. Concave minimum cost network flow problems solved with a colony of ants. Journal of Heuristics 19(1): 1-33 (2013).
Ravizza, S., J.A. Atkin, & E.K. Burke. A more realistic approach for airport ground movement optimization with stand holding. Journal of Scheduling 17(5): 507-520 (2014).
Sada, A.N. & A. Maldonado. Research Methods In Education. British Journal of Educational Studies 55(4): 469-470 (2007).
Sumathi, S., & T. Hamsapriya. Evolutionary Intelligence an Introduction to Theory and Applications with Matlab. Springer, Berlin (2008).
Thevenin, S., N. Zufferey, & M. Widmer. Metaheuristics for a scheduling problem with rejection and tardiness penalties. Journal of Scheduling 18(1): 89-105 (2015).
Tseng, S.P., C.W. Tsai,J.L. Chen, M.C. Chiang, & C.S. Yang. Job shop scheduling based on ACO with a hybrid solution construction strategy. Fuzzy Systems (FUZZ), 2011 IEEE International Conference on Fuzzy Systems p. 2922-2927.IEEE (2011).
Umer, M., R. Ahmad, & S.I. Butt. Intelligent pheromone up gradation mechanism through Neural augmented Ant Colony Optimization (NaACO) metaheuristic in machine scheduling. Scientia Iranica 21 (5): 1726-173 (2014).
Umer, M., R. Ahmad, & I. Chaudhry. Unsupervised Artificial Neural Networks (ANNs) For Intelligent Pheromone up Gradation. Further Evolution of Neural Augmented Ant Colony Optimization (NaACO). Life Science Journal 10(3): 318-327 (2013).
Vidal , T., T.G. Crainic, M. Gendreau,& C. Prins. Time-window relaxations in vehicle routing heuristics. Journal of Heuristics 21 (3): 329-358 (2015).
Zhang, X., & S. van de Velde. Two-machine interval shop scheduling with time lags. Journal of Scheduling 1-10 (2013).
Zhang, X., X. Chen, & Z. He. An ACO-based algorithm for parameter optimization of support vector machines. Expert Systems with Applications 37 (9): 6618-6628 (2010).
Alam, M.A. Techno-stress and productivity: Survey evidence from the aviation industry. Journal of Air Transport Management 50: 62-70 (2016).
