An approximation solution for scheduling problem in single machine under unavailability constraints

Selt, Omar; Benouadah, Hachemi

International Journal of Advanced and Applied Sciences

Int. j. adv. appl. sci.

EISSN: 2313-3724

Print ISSN: 2313-626X

Volume 3, Issue 12 (December 2016), Pages: 1-4

Title: An approximation solution for scheduling problem in single machine under unavailability constraints

Author(s): Omar Selt ^1,*, Hachemi Benouadah ²

Affiliation(s):

¹Laboratory of Pure and Applied Mathematics, Department of Mathematics, University of M'sila, Algeria
²Laboratory of Economic Policies and Strategies in Algeria, Department of Financials Sciences and Accounting, University of M'sila, Algeria

https://doi.org/10.21833/ijaas.2016.12.001

Full Text - PDF XML

Abstract:

In this paper, an approximation solution for scheduling problem of n tasks on single machine with unavailability zones is proposed. This problem is strongly NP-complete which makes finding an optimal solution looks impossible task. In this frame, we suggested a heuristic (H1) in which availability periods of machine are filled with the highest weighted tasks. To improve the performance of this heuristic, we used, on one hand, different diversification strategies E1and E2 with the aim of exploring unvisited regions of the solution space, and on the other hand, two neighborhoods (neighborhood by swapping and neighborhood by insertion). The computational experiment was carried out on single machine with different unavailability zones. It must be noted that tasks movement can be within one period or between different periods.

This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Keywords: Scheduling, Single machine, Heuristic, Metaheuristic, Tabu search

Article History: Received 15 September 2016, Received in revised form 10 November 2016, Accepted 17 November 2016

Digital Object Identifier: https://doi.org/10.21833/ijaas.2016.12.001

Citation:

Selt O and Benouadah H (2016). An approximation solution for scheduling problem in single machine under unavailability constraints. International Journal of Advanced and Applied Sciences, 3(12): 1-4

http://www.science-gate.com/IJAAS/V3I12/Selt.html

References:

Chang PC, Chen SH, Lie T and Liu JYC (2011). A genetic algorithm enhanced by dominance properties for single machine scheduling problems with setup costs. International Journal of Innovative Computing, Information and Control, 7(5): 1-21.

Ho JC and Chang YL (1995). Minimizing the number of tardy jobs for m parallel machines. European Journal of Operational Research, 84(2): 343-355. https://doi.org/10.1016/0377-2217(93)E0280-B

M'Hallah R and Bulfin RL (2005). Minimizing the weighted number of tardy jobs on parallel processors. European Journal of Operational Research, 160(2): 471-484. https://doi.org/10.1016/j.ejor.2003.06.027

Selt O and Zitouni R (2014). A comparative study of heuristic and metaheuristic for three identical parallel machines. Canadian Journal of Pure and Applied Science, 8(3): 3147-3153.

Smith WE (1956). Various optimizers for single‐stage production. Naval Research Logistics Quarterly, 3(1‐2): 59-66. https://doi.org/10.1002/nav.3800030106

Zitouni R and Selt O (2015). Metaheuristics to solve a tasks scheduling problem in parallel identical machines with unavailability periods. RAIRO-Operations Research, 50(1): 83-90. https://doi.org/10.1051/ro/2015013

Zribi N, Kacem I, El-Kamel A and Borne P (2005). Minimisation de la somme des retards dans un jobshop flexible. Revue e-STA (SEE), 2(2): 22-27.