Minimizing Completion Time Variance in a Flowshop Scheduling Problem with a Learning Effect

Abstract

In this paper, flowshop scheduling problem with a learning effect is considered. The objective function of the problem is minimizing completion times variance. A non-linear programming model is developed for the problem. Also the model is tested on an example. Results of computational tests show that the proposed model is effective in solving problems with up to 30 jobs. The overall average solution error of the heuristic algorithm is 2 %. Processing of the 30 jobs case requires only 0.1 s on average to obtain an ultimate or even optimal solution. To solve the large sizes problems up to 500 jobs, heuristics methods were used. The performances of heuristics about the solution error were evaluated with the non-linear programming model results for small size problems and each other for large size problems. According to results, the special heuristic for all number of jobs was the more effective than others. The heuristic scheduling algorithm is more practical to solve real world applications than the non-linear programming model.

 

Key words: flowshop scheduling, learning effect, completion time variance, non-linear programming model, heuristic methods

Keywords

• flowshop scheduling, learning effect, completion time variance, non-linear programming model, heuristic methods

References

1. Merten, A.G., Muller, minimization in single machine sequencing problems”, Management Science, 18: 518–528, (1972). M.E., “Variance
2. Viswanathkumar, G., Srinivasan, G., “A branch and bound algorithm to minimize completion time variance on a single processor”, Computers & Operations Research, 30: 1135–1150, (2003).
3. Schrage, L., “Minimizing the time-in-system variance for a finite jobset”, Management Science, 21: 540–543, (1975).
4. Hall, N.G., Kubiak, W.. “Proof of a conjecture of Schrage about the completion time variance problem”, Operations Research Letters, 14: 467– 472, (1991)
5. Eilon, S., Chowdhury, I.C. “Minimizing the waiting time variance in the single machine problem”, Management Science, 23: 567–575, (1977).
6. Bagchi, U., Chang, Y.L., Sullivan, R.S., “Minimizing absolute and squared deviation of completion times with different earliness and tardiness penalties and a common due date”, Naval Research Logistics, 34: 739–751, (1987).
7. Gupta, M.C., Gupta, Y.P., Bector, C.R., “Minimizing the flow-time variance in single- machine systems”, Journal of Operational Research Society, 41: 767–779, (1990).
8. Mittenthal, J., Raghavachari, M., Rana, A.I., “A hybrid simulated annealing approach for single machine scheduling problems with non-regular penalty functions”, Computers & Operations Research, 20: 103–111, (1993).

9. Gupta, M.C., Gupta, Y.P., Kumar, A., “Minimizing flowtime time variance in single machine systems using genetic algorithms”, European Journal of Operational Research, 70: 289–303, (1993).
10. Ventura, J., Weng, M.X., “Minimizing single machine completion time variance”, Management Science, 41: 1448–1455, (1995).
11. Manna, D.K., Prasad, V.R., “Bounds for the position of the smallest job in completion time variance minimization”, European Journal of Operational Research, 114: 411–419, (1999).
12. De, P., Ghosh, J.B., Wells, C.E., “On the minimization of completion time variance with a bicriteria extension”, Operations Research, 40: 1148–1155, (1992).
13. Prasad, V.R., Manna, D.K., Arthanari, T.S., “A note on the lower bound for completion time variance in Operations Research, 34: 277–282, (1997). scheduling”,
14. Federgruen, A., Mosheiov, G., “Heuristics for multi-machine scheduling problems with earliness and tardiness costs”, Management Science, 42: 1544–1555, (1996).
15. Gajpal, Y., Rajendran, C., “An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops”, International Journal of Production Economics, 101: 259–272, (2006).
16. Biskup, D., “Single machine scheduling with learning considerations”, European Journal of Operational Research, 115: 173¯178, (1999).
17. Mosheiov, G., “Scheduling problems with learning effect”, European Journal of Operational Research, 132: 687¯693, (2001).
18. Mosheiov, G., “Parallel machine scheduling with learning effect”, Journal of The Operational Research Society, 52: 1165-1169, (2001).
19. Eren, T., Güner, E., “Flowshop scheduling with general job-dependent learning effect”, K.H.O. Journal of Defense Science, 2: 1-11, (2003).
20. Johnson, S.M., “Optimal two-and three-stage production schedules with setup times included”, Naval Research Logistics, 1: 61–68, (1954).
21. Lee, W.C., Wu C.C., “Minimizing total completion time in a two-machine flowshop with a learning effect”, International Journal of Production Economics, 88: 85–93, (2004).
22. Eren, T., Güner, E., “Minimizing mean flow time in a flowshop scheduling with learning effect”, Journal of the Faculty of Engineering and Architecture of Gazi University, 19: 119-124, (2004).
23. Lee, W.C., Wu, C.C., Sung, H.J., “A bi-criterion single-machine scheduling problem with learning considerations”, Acta Informatica, 40: 303–315 (2004).
24. Eren, T., Güner, E., “Minimizing total tardiness in a scheduling problem with a learning effect”, Applied Mathematical Modelling, 31(7): 1351- 1361, (2007).
25. Eren, T., Güner, E., “A bicriteria scheduling with a learning effect: total completion time and total tardiness”, INFOR: Information Systems and Operational Research, 45(2): 75-81, (2007).
26. Eren, T., Güner, E., “A bicriteria flowshop scheduling with a learning effect”, Applied Mathematical Modelling, 32(9): 1719-1733, (2008).
27. Xu, Z., Sun, L., Gong, J., “Worst-case analysis for flow shop scheduling with a learning effect”, International Journal of Production Economics, 113: 748–753, (2008).
28. Wang, J.-B., “Flow shop scheduling jobs with position dependent processing times”, Journal of Applied Mathematics and Computing, 18: 383– 391, (2005).
29. Wu, C.C., Lee, W.C., “A note on the total completion time problem in a permutation flowshop with a learning effect”, European Journal of Operational Research, 192: 343–347, (2009).
30. Wang, J.B., Liu, L.L., “Two-machine flow shop problem with effects of deterioration and learning”, Computers & Industrial Engineering, 57: 1114–1121. (2009).
31. Cheng, T.C.E., Wu, C.C., Chen, J.C., Wu, W.H., Cheng, S.R., “Two-machine flowshop scheduling with a truncated learning function to minimize the makespan”, International Journal of Production Economics,141 (1): 79-86, (2013).
32. Kuo, W.H., Hsu, C.J., Yang, D.L., “Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time- dependent learning effect”, Information Sciences, 184: 282–297, (2012). [33] Kubiak, W., “Completion minimization on a single machine is difficult”, Operations Research Letters, 14: 49–59, (1993).
33. Chou, F.D., Lee, C.E., “Two-machine flowshop scheduling with bicriteria problem”, Computers & Industrial Engineering, 36: 549–564, (1999).
34. Eren T., Güner E., Setup times with a learning effect in flowshop scheduling problem”, Journal of the Faculty of Engineering and Architecture of Gazi University, 22 (2): 353-362, (2007).
35. Eren, T., “A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect”, Applied Mathematics and Computation, 209 (2): 186-190, (2009).
36. Eren, T., “Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect”, Applied Mathematics and Computation, 208 (2): 355-358, (2009).
37. Eren T., “A bicriteria parallel machine scheduling with a learning effect of setup and removal times” Applied Mathematical Modelling, 33 (2): 1141- 1150, (2009).
38. Nawaz, M., Enscore, E.E., Ham, I., “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem”, Omega, 11: 91–95, (1983).