A New Fuzzy Hybrid Dynamic Programming for Scheduling Weighted Jobs on Single Machine

Mirmohseni, Seyedeh Maedeh; Nasseri, Seyed Hadi; Khaviari, Mohammad Hossein

doi:10.22105/jarie.2017.49214

Document Type : Research Paper

Authors

¹ School of Mathematics and Information Science, Guangzhou University, Guangzhou, China.

² Department of Operations Research, Faculty of Mathematical Sciences, University of Mazandaran

³ Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Mazandaran, Iran.

https://doi.org/10.22105/jarie.2017.49214

Abstract

In this paper, dynamic programming for sequencing weighted jobs on a single machine to minimizing total tardiness is focused, to significance of fuzzy numbers field, and importance of that for decision makers who are facing on uncertain data, combination of dynamic programming and fuzzy numbers is applied. A random scheduling problem with fuzzy processing times is given and solved. In addition, algorithm consuming time during solving same category problem and different sizes are analyzed that for large problem CPU time usage is extremely unaffordable. Therefore demonstration of near-exact heuristic method such as Genetic Algorithm (GA) appears. In this paper sufficient discussion around solving this kind of problems and their algorithms analysis and a combination between Dynamic Programming (DP) and genetic algorithm as a newly born method is proposed that stand on DP performance and genetic algorithm search power, and finally comparison on the recent developed method has been held. Then this method can deal with real-world problem easily. Thus, decision makers actually can use this modification of dynamic programming for coping with un-crisp problem.

Keywords

Main Subjects

Fuzzy optimization

References

[1] Bellman, R. (2013). Dynamic programming. Courier Corporation.

[2] Ebrahimnejad, A., Nasseri, S. H., Lotfi, F. H., & Soltanifar, M. (2010). A primal-dual method for linear programming problems with fuzzy variables. European Journal of Industrial Engineering, 4(2), 189-209.

[3] Nasseri, S. H., & Ebrahimnejad, A. (2010). A fuzzy primal simplex algorithm and its application for solving flexible linear programming problems. European Journal of Industrial Engineering, 4(3), 372-389.

[4] Mahdavi-Amiri, N., & Nasseri, S. H. (2007). Duality results and a dual simplex method for linear programming problems with trapezoidal fuzzy variables. Fuzzy sets and systems, 158(17), 1961-1978. R.E. [5] Bellman, R. E., & Zadeh, L. A. (1970). Decision-making in a fuzzy environment. Management science, 17(4), B-141.

[6] Bertsekas, D. P., Bertsekas, D. P., Bertsekas, D. P., & Bertsekas, D. P. (1995). Dynamic programming and optimal control (Vol. 1, No. 2).

[7] Novoa, C., & Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 196(2), 509- 515.

[8] Höfferl, F., & Steinschorn, D. (2009). A dynamic programming extension to the steady state refineryLP. European Journal of Operational Research, 197(2), 465-474.

[9] Xiong, Y., & Rao, S. S. (2005). A fuzzy dynamic programming approach for the mixed-discrete optimization of mechanical systems. Journal of Mechanical Design, 127(6), 1088-1099.

[10] Trzaskalik, T., & Sitarz, S. (2007). Discrete dynamic programming with outcomes in random variable structures. European Journal of Operational Research, 177(3), 1535-1548.

[11] Pal, B. B., & Moitra, B. N. (2003). A goal programming procedure for solving problems with multiple fuzzy goals using dynamic programming. European Journal of Operational Research, 144(3), 480- 491.

[12] Safaei, N., Saidi-Mehrabad, M., Tavakkoli-Moghaddam, R., & Sassani, F. (2008). A fuzzy programming approach for a cell formation problem with dynamic and uncertain conditions. Fuzzy Sets and Systems, 159(2), 215-236.

[13] Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.

[14] Lee, K. Y., & El-Sharkawi, M. A. (Eds.). (2008). Modern heuristic optimization techniques: theory and applications to power systems (Vol. 39). John Wiley & Sons.

[15] Eberhart, R. C., & Shi, Y. (2007). Computational intelligence. Morgan Kaufmann.

[16] Malandraki, C., & Dial, R. B. (1996). A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90(1), 45- 55.

[17] Park, Y. M., Park, J. B., & Won, J. R. (1998). A hybrid genetic algorithm/dynamic programming approach to optimal long-term generation expansion planning. International Journal of Electrical Power & Energy Systems, 20(4), 295-303.

[18] Patra, S., Goswami, S. K., & Goswami, B. (2009). Fuzzy and simulated annealing based dynamic programming for the unit commitment problem. Expert Systems with Applications, 36(3), 5081-5086.

[19] Tang, L., & Ren, H. (2010). Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem. Computers & Operations Research, 37(2), 368-375.

[20] Ibaraki, T., & Nakamura, Y. (1994). A dynamic programming method for single machine scheduling. European Journal of Operational Research, 76(1), 72-82.

[21] Li, D. C., & Li, T. Y. (1988). An algorithm for sequencing jobs to minimize total tardiness. Journal of the Chinese Institute of Engineers, 11(6), 653-659.

[22] Jinjiang, Y. U. A. N. (1992). The NP-hardness of the single machine common due date weighted tardiness problem, Syst. Sci. Math. Sci, 5, 328–333.

[23] Tuong, N. H., Soukhal, A., & Billaut, J. C. (2010). A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines. European Journal of Operational Research, 202(3), 646-653.

[24] Bosio, A., & Righini, G. (2009). A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times. Mathematical methods of operations research, 69(2), 271.

[25] Koulamas, C. (2009). A faster fully polynomial approximation scheme for the single-machine total tardiness problem. European Journal of Operational Research, 193(2), 637-638.

[26] Kacem, I. (2010). Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date. Discrete Applied Mathematics, 158(9), 1035-1040.

[27] Kacem, I. (2010). Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date. Discrete Applied Mathematics, 158(9), 1035-1040.

[28] Khorshidian, H., Javadian, N., Zandieh, M., Rezaeian, J., & Rahmani, K. (2011). A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert systems with applications, 38(7), 7911-7918.

[29] Bilge, Ü., Kurtulan, M., & Kıraç, F. (2007). A tabu search algorithm for the single machine total weighted tardiness problem. European Journal of Operational Research, 176(3), 1423-1435.

[30] Xu, K., Feng, Z., & Jun, K. (2010). A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates. Computers & Operations Research, 37(11), 1924-1938.

[31] Valente, J. M. (2007). Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties. Computers & Industrial Engineering, 52(4), 434-447.

[32] Liu, L., & Zhou, H. (2013). Hybridization of harmony search with variable neighborhood search for restrictive single-machine earliness/tardiness problem. Information Sciences, 226, 68-92.

[33] Altunc, A. B. C., & Keha, A. B. (2009). Interval-indexed formulation based heuristics for single machine total weighted tardiness problem. Computers & Operations Research, 36(6), 2122-2131.

[34] Lee, J. Y., & Kim, Y. D. (2012). Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Computers & Operations Research, 39(9), 2196-2205.

[35] Panneerselvam, R. (2006). Simple heuristic to minimize total tardiness in a single machine scheduling problem. The International Journal of Advanced Manufacturing Technology, 30(7), 722-726.

[36] Yoon, S. H., & Lee, I. S. (2011). New constructive heuristics for the total weighted tardiness problem. Journal of the Operational Research Society, 62(1), 232-237.

[37] Yager, R. R. (1981). A procedure for ordering fuzzy subsets of the unit interval. Information sciences, 24(2), 143-161.

[38] Chang, P. C., Chen, S. H., & Mani, V. (2009). A note on due-date assignment and single machine scheduling with a learning/aging effect. International Journal of Production Economics, 117(1), 142- 149.

Journal of Applied Research on Industrial Engineering

A New Fuzzy Hybrid Dynamic Programming for Scheduling Weighted Jobs on Single Machine

References

References

Volume 4, Issue 2 - Serial Number 2
October 2017
Pages 97-115

A New Fuzzy Hybrid Dynamic Programming for Scheduling Weighted Jobs on Single Machine

References

References

Volume 4, Issue 2 - Serial Number 2October 2017Pages 97-115

Volume 4, Issue 2 - Serial Number 2
October 2017
Pages 97-115