Scheduling of Jobs on Identical Parallel Machines to Minimize Total Flow Time Subject to Optimal Makespan

Abstract:

Algorithms based on Simulated Annealing and Tabu search has been proposed and implemented on scheduling a problem of parallel machines. The identical parallel machine scheduling problem has been considered to minimize the total flow-time subject to optimal makespan. The proposed algorithms have two phases. In the first phase, an initial solution has been obtained using Longest Processing Time (LPT) dispatching rule and in the second phase, simulated annealing and tabu search have been applied to reach a near optimal solution. The performance of the both proposed algorithms have been evaluated by comparing their results for different number of jobs and processing times. The computational results indicate that the proposed Tabu Search algorithm is capable of obtaining better solutions for the given scheduling problem as compared to the Simulated Annealing algorithm. Although both of these algorithms provide the best solutions as compared to the other heuristic algorithms but in comparison of these two; Tabu Search provides the better solutions for the given problem.

• Periodical: Advanced Materials Research (Volume 903)
• Pages: 390-395
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.903.390
• Online since: February 2014
• Authors: Muhammad Usman Aslam*, Mustafa Mohamed H. Nasr, Ibrahim Alharkan
• Keywords: Bi-Criteria, Identical Parallel Machines, Make Span, Scheduling, Sequencing, Simulated Annealing (SA), Tabu Search, Total Flow Time

References

[1] Ho JC, Wong JS, Makespan Minimization for Parallel Identical Processors, Naval Research Logistics (1995) 42: 935-48.

DOI: 10.1002/1520-6750(199509)42:6<935::aid-nav3220420606>3.0.co;2-d

[2] Jatinder N. D. Gupta, Johnny C. Ho, Minimizing Flowtime Subject to Optimal Makespan on Two Identical Parallel Machines, Pesquisa Operacional-5, junho de (2000), Vol. 20, No. 1.

DOI: 10.1590/s0101-74382000000100003

[3] Johnny C. Ho, Francisco J. López, Alex J. Ruiz-Torres, Tzu-Liang (Bill) Tseng, Minimizing Total Weighted Flowtime Subject to Minimum Makespan on two Identical Parallel Machines, Springer Science+Business Media, LLC (2009).

DOI: 10.1007/s10845-009-0270-1

[4] Chien-Hung Lina, Ching-Jong Liao, Makespan Minimization Subject to Flowtime Optimality on Identical Parallel Machines, Computers & Operations Research 31 (2004) 1655–1666.

DOI: 10.1016/s0305-0548(03)00113-8

[5] Ethel Mokotoff , An Exact Algorithm for the Identical Parallel Machine Scheduling Problem, European Journal of operational Research 152 (2004) 758-769.

DOI: 10.1016/s0377-2217(02)00726-9

[6] Mauro Dell'Amico, Silvano Martello, A Note on Exact Algorithms for the Identical Parallel Machine Scheduling Problem, European Journal of operational Research (2005).

DOI: 10.1016/j.ejor.2004.06.002

[7] Wen-Chiung Lee. Chin-Chia Wu. Peter Chen, A Simulated Annealing Approach to Makespan Minimization on Identical Parallel Machines, Springer-Verlag London Limited (2005).

[8] Persson, Rasmus, A Bicriteria Simulated Annealing Algorithm for Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times, European Journal of Operational Research 187, 985-1032 (2008).

[9] Johnny C. Ho, Francisco J. López, Alex J. Ruiz-Torres, Tzu-Liang (Bill) Tseng, Minimizing Total Weighted Flowtime Subject to Minimum Makespan on two Identical Parallel Machines, Springer Science+Business Media, LLC (2009).

DOI: 10.1007/s10845-009-0270-1

[10] Pinedo. M, Scheduling: Theory. Algorithms and Systems, Prentice Hall, Englewood Cliffs, NJ, (1995).