Solving Machine Scheduling Problem under Fuzzy Processing Time using the Simulated Annealing Method

Al-Zuwaini Mohammed Kadhim, Shaker K. Ali, Marwa Mohammed Kassim

Abstract


In this paper, we describe the problem of sequencing a set of n jobs on single machine was considered to minimize multiple objectives function (MOF). The objective is to find the approximate solutions for scheduling n independent jobs to minimize the objective function consists from a sum of weighted number of early jobs and the weighted number of tardy jobs with fuzzy processing time. This problem is denoted by: (1/ / ). To resolve it we proposed the Average High Ranking (AHR) method to obtain a processing time generated from fuzzy processing time, calculate the costs and reach to total penalty cost. Since our problem is Strongly NP-hard in normal form, we used Simulated Annealing. It solved the problem with up to 12000 jobs in 30 seconds.


Keywords


Scheduling; Single machine; Fuzzy processing time; Simulated Annealing Heuristics; Weighted number of early jobs; Weighted number of tardy jobs.

Full Text:

PDF

References


Gupta, S. and Rambha, M. (2011). Single Machine Scheduling With Distinct Due Dates Under Fuzzy Environment; International Journal of Enterprise Computing and Business Systems, vol. 1, no. 2, pp. 1–9.

Baker, K.R. and Scudder, G.D. (1990). Sequencing with Earliness and Tardiness Penalties: A Review; Operations Research, Vol. 38, No.21, Pp. 22-36.

Soroush, H. (2007). Minimizing the Weighted Number of Early and Tardy Jobs in a Stochastic Single Machine Scheduling Problem; European Journal of Operational Research, Vol. 181, No. 1, Pp. 266–287.

Pinedo, M.L. (2016). Scheduling: Theory, Algorithms, and Systems; 5th Edition, Springer, New York.

Al-Harkan, I.M. (1997). Algorithms for Sequencing and Scheduling; University of Riyadh, College of Engineering, Industrial Engineering Department, King Saud, Riyadh, Saudi Arabia, Ch. 8, Pp. 8-1, 8-19.

Kirkpatrick, S. Gelatt Jr, C.D. and Vecchi, M.P. (1983). Optimization by Simulated Annealing; Science, Vol. 220, No. 4598, Pp. 671–680,

Černý, V. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm; Journal ofOptimization Theory and Applications, Vol. 45, No. 1, Pp. 41–51.

Metropolis, N. Rosenbluth, A.W. Rosenbluth, M.N. Teller, A.H. and Teller, E. (1953). Equation of State Calculations by Fast Computing Machines; The Journal of Chemical Physics, Vol. 21, No. 6, Pp. 1087-1092.

Abdul-Razaq, T.S. Potts, C.N. and Van, Wassenhove. (1990). A survey of Algorithms for The Single Machine Total Weighted Tardiness Scheduling Problem; Discrete App. Math. Pp. 26235-253.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Journal of Progressive Research in Mathematics

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright © 2016 Journal of Progressive Research in Mathematics. All rights reserved.

ISSN: 2395-0218.

For any help/support contact us at editorial@scitecresearch.com, jprmeditor@scitecresearch.com.