Performance enhancement of numerical approaches for scheduling problem on machine single
Article Sidebar
Main Article Content
صندلی اداریAbstract
In this paper, we consider a single-machine scheduling problem, with the aim of minimizing the weighted sum of the completion time. This problem is NP-hard, making the search for an optimal solution very difficult. In this frame, two heuristics (H1), (H2) and metaheuristic tabu search are suggested.
To improve the performance of this techniques, we used, on one hand, different diversification strategies (TES1 and TES2) with the aim of exploring unvisited regions of the solution space. On the other hand, we suggested three types of neighborhoods (neighborhood by swapping, neighborhood by insertion and neighborhood by blocks).It must be noted that tasks movement can be within one period or between different periods.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
1. Proposal of Policy for Free Access Periodics
Authors whom publish in this magazine should agree to the following terms:
a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 that allows the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.
b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in an institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.
c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).
Proposal of Policy for Periodic that offer Postponed Free Access
Authors whom publish in this magazine should agree to the following terms:
a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 [SPECIFY TIME HERE] after the publication, allowing the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.
b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.
c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).
d. They allow some kind of open dissemination. Authors can disseminate their articles in open access, but with specific conditions imposed by the editor that are related to:
Version of the article that can be deposited in the repository:
Pre-print: before being reviewed by pairs.
Post-print: once reviewed by pairs, which can be:
The version of the author that has been accepted for publication.
The editor's version, that is, the article published in the magazine.
At which point the article can be made accessible in an open manner: before it is published in the magazine, immediately afterwards or if a period of seizure is required, which can range from six months to several years.
Where to leave open: on the author's personal web page, only departmental websites, the repository of the institution, the file of the research funding agency, among others.
References
Abdenacer, G. (2014). metaheuristic algorithms for solving quadratic assignment problem, IJACSA, 5, 15-21.
Adamu M. O., & Adewunmi. A. (2013).Comparative study of meta-heuristics for identical parallel machines, J. Eng. Technol. Res., 5(7), 207-216.
Chang, P.-C., Chen, S.-H., Lie, T., & Liu, J. Y.-C. (2011). A genetic algorithm enhanced by dominance properties for single machine scheduling problems with setup costs, International Journal of Innovational Computing Information and Control, 7(5A), 2323–2344.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533-549.
Glover, F., & S. Hanafi, S. (2002). Tabu Search and Finite Convergence, Special Issue on Foundations of heuristics in Combinatorial Optimization. Discrete Appl. Math, 119, 3-36.
Hansen, P. (2006). The steepest ascent mildest descent heuristic for combinatorial programming, Proceedings of the Congress on Numerical Methods, Capri, Italy.
Haouari. M., & Ladhari, T. (2003). A branch-and-bound-based local search method for the flow shop problem, J. Oper. Res. Soc., 54, 1076-1084. DOI: 10.1057/palgrave.jors.2601612
Lee. C. Y. (1996). Machine scheduling with an availability constraints, J. Global Optim., 9, 395-416.
Lee C. Y. (1997). Minimising the makespan in two machines flow shop scheduling problem with availability constraints, Oper. Res. Lett., 20, 129-139.
M'Hallah, R., & Bulfin, R. L. (2005). Minimizing the weighted number of tardy jobs of parallel processors, Eur. J. Oper. Res., 160, 471-4847.
Sakarovitch, M. (1984). Optimisation combinatoire: Programmation discrete, Hermann, France.
Schmidt, G. (2000). Scheduling with limited machine availability, European J. Oper, 121, 1-15.
Selt, O., & Zitouni, R. (2014). A comparative study of heuristic and metaheuristic for three identical parallel machines, Cjpas, 3147-3153.
Smith, W. E. (1956). Various optimizes for single-stage production, NavaRes.Logist, 3, 59-66.
Liang, Y.-C., Hsiao, Y.-M., & Tien, C.-Y. (2013) Metaheuristics for drilling operation scheduling in Taiwan PCB industries, International Journal of Production Economics, 141(1), 189-198. DOI: 10.1016/j.ijpe.2012.04.014
Zribi, N., Kacem, I., El-Kamel, A., & Borne, P. (2005). Minimisation de la somme des retards dans un job shop flexible, Revue e-STA (SEE), 6(6), 21-25.
Zitouni, R., & Selt, O. (2016). Metaheuristics to solve tasks scheduling problem in parallel identical machines with unavailability periods, RAIRORes, 50(1), 90.