Minimización de la tardanza en problemas de programación de tareas en maquinas paralelas con deterioro de los recursos
Palabras clave:
Deterioro de máquinas, fechas de entrega, tardanza, máquinas paralelas, programación de operaciones, heurísticas.Resumen
En ambientes de manufactura y de servicios es frecuente encontrar diferentes tareas que son realizadas en paralelo empleando recursos heterogéneos, los cuales tienen la característica de sufrir deterioro a medida que transcurre el tiempo. Ese deterioro tiene un impacto significativo en el desempeño de dichos recursos, lo que se puede medir de diferentes formas tales, como: calidad, tiempo de proceso, entre otros. Esta investigación científica utiliza un modelo donde el deterioro de los recursos es una función de las tareas específicas previamente realizadas por el recurso. La formulación del problema se presenta por medio de un modelo de programación matemática. Este trabajo presenta dos heurísticas para resolver el problema en un tiempo razonable, donde cada heurística emplea diferentes reglas y criterios para identificar la mejor solución. Un análisis de sensibilidad, que comprende 2700 casos, es llevado a cabo para evaluar la eficacia de las heurísticas. Los resultados comprueban que las heurísticas son eficientes y generan soluciones útiles para el tomador de decisiones.
In manufacturing and service environments it is common to find processes that are performed in parallel by different resources, which have the characteristic that their performance deteriorates with time. This deterioration has a significant effect on the performance of the resources that can be measured in different forms such as quality and process time. This research utilizes a model where resource deterioration is a function of the specific jobs previously completed by the resource. The problem’s formulation is presented as a mathematical program. The paper presents two heuristics to solve the problem, where each has different rules to find the best solution. A sensitivity analysis that includes 2700 cases is performed to evaluate the performance of the heuristics. The results demonstrate that the heuristics are efficient and generate useful solutions for decision makers.
Descargas
Citas
ALIDAEE, B., and WOMER, N.K. Scheduling with time dependent processing times: review and extensions. Journal of the Operational Research Society, 1999, vol. 50, no. 7, p. 711-720.
ANGHINOLFI, D., and PAOLUCCI, M. Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Computers & Operations Research, 2007, vol. 34, no. 11, p. 3471-3490.
AZIZOGLU, M., and KIRCA, O. Tardiness minimization on parallel machines. International Journal of Production Economics, 1998, vol. 55, no. 2, p. 163-168.
BANK, J., and WERNER, F. Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Mathematical and Computer Modelling, 2001, vol. 33, no. 4, p. 363-383.
BILGE, Ü., KIRAÇ, F., KURTULAN, M., and PEKGÜN, P. A tabu search algorithm for parallel machine total tardiness problem. Computers & Operations Research, 2004, vol. 31, no. 3, p. 397-414.
BISKUP, D., and HERRMANN, J. Single-machine scheduling against due dates with pastsequence-dependent setup times. European Journal of Operational Research, 2008, vol. 191, no. 2, p. 587-592.
BISKUP, D., HERRMANN, J., and GUPTA, J.N. Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics, 2008, vol. 115, no. 1, p. 134-142.
BROWNE, S., and YECHIALI, U. Scheduling deteriorating jobs on a single processor. Operations Research, 1990, vol. 38, no. 3, p. 495-498.
CHENG, T.E., DING, Q., and LIN, B.M. A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 2004, vol. 152, no. 1, p. 1-13.
CHENG, T.E., HSU, C.J., HUANG, Y.C., and LEE, W.C. Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness. Computers & Operations Research, 2011, vol. 38, no. 12, p. 1760-1765.
CHENG, M., TADIKAMALLA, P.R., SHANG, J., and ZHANG, S. Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. European Journal of Operational Research, 2014, vol. 234, no. 3, p. 650-667.
DELLA CROCE, F., GARAIX, T., and GROSSO, A. Iterated local search and very large neighborhoods for the parallel-machines total tardiness problem.Computers & Operations Research, 2012, vol. 39, no. 6, p. 1213-1217.
EREN, T., and GÜNER, E. Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling, 2007, vol. 31, no. 7, p. 1351-1361.
GUPTA, J.N., and GUPTA, S. K. Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 1988, vol. 14, no. 4, p. 387-393.
HO, J.C., and CHANG, Y.L. Heuristics for minimizing mean tardiness for m parallel machines. Naval Research Logistics (NRL), 1991, vol. 38, no. 3, p. 367-381.
HUANG, X., and WANG, M. Z. Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Applied Mathematical Modelling, 2011, vol. 35, no. 3, p. 1349-1353.
JOO, C.M., and KIM, B.S. Genetic algorithms for single machine scheduling with time-dependent deterioration and rate-modifying activities.Expert Systems with Applications, 2013, vol. 40, no. 8,p. 3036–3043.
JOUGLET, A., and SAVOUREY, D. Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates. Computers & Operations Research, 2011, vol. 38, no. 9, p. 1259-1266.
LIAW, C.F., LIN, Y.K., CHENG, C.Y., and CHEN, M. Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers & Operations Research, 2003, vol. 30, no. 12, p. 1777-1789.
LIU, M., ZHENG, F., WANG, S., and XU, Y. Approximation algorithms for parallel machine scheduling with linear deterioration. Theoretical Computer Science, 2013, vol. 497, no. 29, p.108–111.
MAZDEH, M. M., ZAERPOUR, F., ZAREEI, A., and HAJINEZHAD, A. Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs. Applied Mathematical Modelling, 2010, vol. 34, no. 6, p. 1498-1510.
MOSHEIOV, G.A note: Multi-machine scheduling with general position-based deterioration to minimize total load. International Journal of Production Economics, 2012, vol. 135, no. 1, pp. 523-525.
RUIZ-TORRES, A. J., PALETTA, G., and PÉREZ, E. Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects. Computers & Operations Research, 2013, vol. 40, no. 8, p. 2051–2061.
SHIM, S.O., and KIM, Y.D. Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research, 2007, vol. 177, no. 1, p. 135-146.
STERNA, M.A survey of scheduling problems with late work criteria. Omega, 2011, vol. 39, no. 2, p. 120-129.
SUN, H., and WANG, G. Parallel machine earliness and tardiness scheduling with proportional weights. Computers & Operations Research, 2003, vol. 30, no. 5, p. 801-808.
TANAKA, S., and ARAKI, M.A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. International Journal of Production Economics, 2008, vol. 113, no. 1, p. 446-458.
TOKSARI, M. D., and GÜNER, E. The common due-date early/tardy scheduling problem on a parallelmachine under the effects of time-dependent learning and linear and nonlinear deterioration. Expert Systems with Applications, 2010, vol. 37, no. 1, p. 92-112.
VELEZ, M., and LÓPEZ, J.A. Variable neighborhood search algorithm to minimize the total weighted tardiness on a batch processing machine.Revista Ingenieria Industrial, 2011, vol. 10, no. 1, p 5-18.
WU, C. C., CHENG, S. R., WU, W. H., YIN, Y., and WU, W. H. The single-machine total tardiness problem with unequal release times and a linear deterioration. Applied Mathematics and Computation, 2013a, vol. 219, no. 20, p. 10401–10415.
WU, W. H., XU, J., WU, W. H., YIN, Y., CHENG, I. F., and WU, C. C. A tabu method for a twoagent single-machine scheduling with deterioration jobs.Computers & Operations Research, 2013b, vol. 40, no. 8, p. 2116–2127.
XU, K., FENG, Z., and JUN, K. A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates.Computers & Operations Research, 2010, vol. 37, no. 11, p. 1924-1938.
YALAOUI, F., and CHU, C. Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 2002, vol. 76, no. 3, p. 265-279.
YANG, S. J. Parallel machines scheduling with simultaneous considerations of position-dependent deterioration effects and maintenance activities. Journal of the Chinese Institute of Industrial Engineers, 2011, vol. 28, no. 4, p. 270-280.
YANG, D. L., CHENG, T. C. E., YANG, S. J., and HSU, C. J. Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities. Computers & Operations Research, 2012, vol. 39, no. 7, p. 1458-1464.
YANG, S. J. Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time. Applied Mathematical Modelling, 2013, vol. 37, no. 5, p. 2995–3005.
ZHANG Z., ZHENG, L., LI, N., WANG, W., ZHONG, S., and HU, K. Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning. Computers & Operations Research, 2012, vol. 39, no. 7, pp. 1315-1324.
Descargas
Publicado
Número
Sección
Licencia
Revista Ingeniería Industrial by Revista Ingeniería Industrial is licensed under a Creative Commons Reconocimiento 4.0 Internacional License. Creado a partir de la obra en revistas.ubiobio.cl/index.php/RI/. Puede hallar permisos más allá de los concedidos con esta licencia en http://revistas.ubiobio.cl/index.php/RI/about/
