Research on Parallel Scheduling of Maximize the Number of Task Processing under Time Constraints- an Example to De-Icing Operation

Abstract:

Under the context of airplane deicing, this paper aims to do a research on the unrelated parallel scheduling of service resources with flexible time window. To deal with more tasks, minimizing delay time is chosen to be the objective of the mathematical model and a modified ant colony algorithm is given. With full consideration of the practical problem and constraints, update policy of pheromone and settings of heuristic factors are suggested. The feasibility and rationality are proved by a simulation example. The modified ant colony algorithm outperforms FIFO method and could be well applied in the unrelated parallel scheduling issues with flexible time window.

• Periodical: Applied Mechanics and Materials (Volumes 148-149)
• Pages: 1101-1106
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.148-149.1101
• Online since: December 2011
• Authors: Bing Li, Xin Yue Fu, Dan Su, Gui Song Jiang
• Keywords: Ant Colony Algorithm (ACA), Flexible Time Window, Unrelated Parallel Scheduling

References

[1] Sang-Oh Shim, Yeong-Dae Kim, Scheduling on parallel identical machines to minimize total tardiness[J]. European Journal of Operational Research, Volume 177, Issue 1, 16 February 2007, Pages 135-146.

DOI: 10.1016/j.ejor.2005.09.038

[2] Kai Li, Shan-lin Yang, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms[J]. Applied Mathematical Modelling, Volume 33, Issue 4, April 2009, Pages 2145-2158.

DOI: 10.1016/j.apm.2008.05.019

[3] Michael X. Weng, John Lu, Haiying Ren, Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective[J]. International Journal of Production Economics, Volume 70, Issue 3, 18 April 2001, Pages 215-226.

DOI: 10.1016/s0925-5273(00)00066-9

[4] Vinicius Amaral Armentano, Moacir Felizardo de Franca Filho, Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach[J]. European Journal of Operational Research, Volume 183, Issue 1, 16 November 2007, Pages 100-114.

DOI: 10.1016/j.ejor.2006.09.077

[5] Y.K. Lin, M.E. Pfund, J.W. Fowler, Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems[J]. Computers & Operations Research, 38(2011)901-916.

DOI: 10.1016/j.cor.2010.08.018

[6] Runwei Cheng, Mitsuo Gen, Tatsumi Tozawa, Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms[J]. Computers & Industrial Engineering, Volume 29, Issues 1-4, September 1995, Pages 513-517.

DOI: 10.1016/0360-8352(95)00126-l

[7] Dirk Biskup, Jan Herrmann, Jatinder N.D. Gupta, Scheduling identical parallel machines to minimize total tardiness[J]. Int.J. Production Economics 115(2008) 134-142.

DOI: 10.1016/j.ijpe.2008.04.011

[8] M.J.R. Ebben, M.C. van der Heijden, A. van Harten , Dynamic transport scheduling under multiple resource constraints[J]. European Journal of Operational Research, 167(2005)320–335.

DOI: 10.1016/j.ejor.2004.03.020

[9] Nadia Ranaldo, Eugunio Zimeo, Time and Cost-Driven Scheduling of Data Parallel Tasks in Grid Workflows[J]. IEEE Systems Journal, Vol. 3, No. 1, March (2009).

DOI: 10.1109/jsyst.2008.2011299

[10] D. Antony Louis Piriyakumar, C. Siva Ram Murthy, Optimal Scheduling of Parallel Tasks of Tracking Problem Onto Multiprocessors[J]. IEEE Transactions on Aerospace and Electronic Systems, Vol. 32, No. 2 April (1996).

DOI: 10.1109/7.489515

[11] Ido Juran, Joseph N. Prashker, A dynamic traffic assignment model for the assessment of moving bottlenecks[J]. Transportation research part C (2009).

DOI: 10.1016/j.trc.2008.10.003

[12] Xie Bing-lei, Li Jun, GUO Yao-huang, Genetic algorithm for vehicle scheduling problem of non-full loads with time windows[J]. Journal of Systems Engineering, Vol. 15 No. 3 Sep, (2009).