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

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

Al-Zuwaini Mohammed Kadhim University of Thi-Qar, Iraq
Shaker K. Ali University of Thi-Qar, Iraq
Marwa Mohammed Kassim MS.C student in Thi-Qar university, Iraq

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

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.

Downloads

Download data is not yet available.

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.