Abstract

In this study we propose a new polynomial metaheuristic elaboration (tabu search) for solving scheduling problems. This method allows us to solve the scheduling problem of n Tasks on m identical parallel machines with availability zones (T_z, S_z). Since this problem is NP-complet in the strong sense and finding an optimal solution appears unlikely, we suggested an heuristic based on choosing the most available machine. To improve the performance of this heuristic, we used diversification strategies with the aim of exploring unvisited regions of the solution space and two well-known neighborhoods (neighborhood by swapping and neighborhood by insertion). It must be noted that tasks movement can be within one machine or between different machines. Note that all data in this problem are integer and deterministic. The performance criterion to optimize in this problem which we denote P_m//N-C//Σⁿ_j=1 w_jC_j is the weighted sum of the end dates of tasks.

Keywords:

Metaheuristic , parallel identical machines , scheduling , tabu search , unavailability periods,

References

1. Adamu, M.O. and O. Abaas, 2010. Paralell machine sheduling to maximize the weighted number of just-in-time jobs. J. Appl. Sci. Technol., 15(1/2): 12-34.
   
2. Adamu, M.O. and A. Adewumi, 2012. Metaheuristics for scheduling on parallel machine to minimize weighted number of early and tardy jobs. Int. J. Phys. Sci., 7(10): 1641-1652.
   CrossRef    
3. Adamu, M.O. and A. Adewumi, 2013. Comparative study of metaheuristics for identical parallel machines. J. Eng. Technol. Res., 5(7): 207-216.
   CrossRef    
4. Baptiste, P., A. Jouglet, C.L. Pape and W. Nuijten, 2000. A constrant based approach to minimize the weighted number of late jobs on parallel machines. Technicol Report 2000/228, UMR, CNRS 6599, Heudiasyc, France.
   
5. Belouadah, H., M.E. Posner and C.N. Potts, 1992. Scheduling with relates dates on a single machine to minimize total weighted completion time. Discrete Appl. Math., 36: 213-231.
   CrossRef    
6. Glover, F. and S. Hanafi, 2002. Tabu search and finite convergence, special issue on foundations of heuristics in combinatorial optimization. Discrete Appl. Math., 119: 3-36.
   CrossRef    
7. Hansen, P., 1986. The steepest ascent mildest descent heuristic for combinatorial programming. Proceeding of the Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy.
   
8. Haouari, M. and T. Ladhari, 2003. Branch and bound-based local search method for the flow shop probleme. J. Oper. Res. Soc., 54: 1076-1084.
   CrossRef    
9. Ho, J.C. and Y.L. Chang, 1995. Minimizing the number of tardy jobs for m parallel machines. Eur. J. Oper. Res., 84: 334-355.
   CrossRef    
10. Kacem, I., et al., 2005. Minimising the sum of the completion time with availability constraint: comparaison of branch and bound method and integer linear programming. IESM'05, Marrakech Morocco, pp: 16-19.
    
11. Lee, C.Y., 1996. Machine scheduling with an availability constraints. J. Global Optim., 9: 395-416.
    CrossRef    
12. Lee, C.Y., 1997. Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Oper. Res. Lett., 20: 129-139.
    CrossRef    
13. Lee, C.Y., 1999. Two machines flow shop scheduling problem with availability constraints. Eur. J. Oper. Res., 114: 420-429.
    CrossRef    
14. M'Hallah, R. and R.L. Bulfin, 2005. Minimizing the weighted number of tardy jobs on parallel processors. Eur. J. Oper. Res., 160: 471-484.
    CrossRef    
15. Sadfi, C., 2002. Problèmes d'ordonnancement avec minimisation des encours. Ph.D. Thèse, Institut National Polytechnique de Grenoble, France.
    
16. Sakarovitch, M., 1984. Optimisation Combinatoire: Programmation Discrète. Hermann, France.
    
17. Schmidt, G., 2000. Scheduling with limited machine availability. Eur. J. Oper. Res., 121: 1-15.
    CrossRef    
18. Smith, W.E., 1956. Various optimizes for single-stage production. Nav. Res. Log., 3: 59-66.
    CrossRef    
19. Yun-Chia, L., H. Yu-Ming and T. Chia-Yun, 2013. Metaheuristics for drilling operation scheduling in Taiwan PCB industries. Int. J. Prod. Econ., 141(1): 189-198.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.