Volume 3 Issue 2 pp. 185-198 January, 2013


Heuristics for production scheduling problem with machining and assembly operations


A Bhongade and P.M. Khodke


This work deals with production scheduling problem in an assembly flow shop, having parts machining followed by their subsequent assembly operations. Limited heuristics available on the problem, are based on unrealistic assumption that every part is processed on all machines. In this paper, two heuristics NEH_BB and Disjunctive are proposed to solve assembly flow shop scheduling problem where every part may not be processed on each machine. Exhaustive computational experiments are conducted with 60 trials each. The methods are found to be applicable to large size problems. The objective functions used for comparison are makespan and computational time. Disjunctive method takes very less computational time as compared to NEH_BB and hence claimed to be the better among available approaches for finding solution in assembly flow shop problems.


DOI: 10.5267/j.ijiec.2011.09.003

Keywords: Production scheduling, Assembly flow shop, Makespan, Heuristics

References

Allahverdi A., & Al-Anzi, F. S. (2006). A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers and Operation Research, 33(4), 1056-1080.

Allahverdi, A. & Al-Anzi, F. S. (2007). The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. International Journal of Advance Manufacturing Technology, 37 (1), 166–177.

Allahverdi A., & Al-Anzi, F.S. (2008). The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. International Journal of Advance Manufacturing Technology, 37(1-2), 66-177.

Al-Anzi, F. S. &, Allahverdi, A. (2009). Heuristics for a two-stage assembly flow shop with bicriteria of maximum lateness and makespan. Computers and Operation Research, 36, 2682-2689.

Doctor, S. R., Cavalier, T. M. & Egbelu, P. J. (1993). Scheduling for machining and assembly in a job-shop environment. International Journal of Production Research, 31 (6), 1275-1297.

Fry, T.D., Olife, M.D., Minor, E.D.,& Keong Leong, G. (1989). The effect of product structure and sequencing rule on assembly shop performance, International Journal of Production Research, 27 (4), 671-686.

Hariri, A. M. A., & Potts, C. N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research, 103(3), 547-556.

Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R. & Maboudian, Y. (2010). Two meta-heuristics for three-stage assembly flowshop scheduling with sequence dependent setup times. International Journal of Advance Manufacturing Technology, 50(9-12),1153-1164.

Koulamas, C., & Kyparisis, G.J. (2001). The three-stage assembly flowshop scheduling problem. Computers and Operation Research, 28(7), 689-704.

Lee, C. Y., Cheng, T .C. E., & Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Managment Science JSTOR, 39( 5), 616–625.

Lu, H. L., Huang, G. Q. &Yang, H. D. (2011). Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach. International Journal of Production Research, 49(3), 647–669.

McCoy, D. H. C., & Egbelu, P. J. (1998). Minimizing production flow time in a process and assembly job shop. International Journal of Production Research, 36 (8), 2315-2332.

Moon-Won, P., & Kim, Y. D. (2000). A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints. European Journal of Operational Research,123(3), 504-518.

Nawaz, M., Enscore, Jr. E. E. & Ham, I. (1983). Heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega, International Journal of Management Science, 11(1), 91–95.

Park, M. W., & Kim, Y. D. (1999). A heuristic algorithm for a production planning problem in an assembly system. Journal of Operational Research Society, 50, 138-147.

Pinedo, M. (2002). Scheduling: Theory, Algorithms and Systems, Second ed. Prentice-Hall, Englewood Cliffs, NJ.

Pereira, M. T., & Santoro, M. C. (2011). An integrative heuristic method for detailed operations scheduling in assembly job shop systems. International Journal of Production Research, 1–17, iFirst.

Phadke, M.S. (1989). Quality engineering using robust design. Prentice hall, Englewood Cliff, NJ.

Potts, C.N., Sevast’janov, S.V., Strusevich, V.A., Van, Wassenhove L.N. & Zwaneveld, C.M., (1995). The two stage assembly scheduling problem: complexity and approximation. Operations Research, 43,346–55.

Philipoon, P.R., Russel, R.S. L., & Fry, T.D., (1991). A preliminary investigation of multi-attribute based sequencing rules for assembly shops, International Journal of Production Research, 29 (4), 739-753.

Thiagarajan, S., & Rajendran, C. (2005). Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs. Computers and Industrial Engineering, 49 (4),463–503.

Torabzadeh, E., & Zandieh, M. (2010). Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop. Advance Engineering Software, 41(10-11),1238-1243.

Tozkapan A., Kirca, O., & Chung, C. S. (2003). A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem. Computers and Operations Research, 30(2), 309-320.

Yokoyama, M. (2001). Hybrid flow shop scheduling with assembly operations. International Journal of Production Economics, 73(1), 103-116.

Yokoyama, M. & Santos, D. L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161(3), 754-770.

Yokoyama, M .(2008). Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research, 187(3), 1184-1195.

Xi , S., Morizawa, K., & Nagasawa, H. (2003). Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling European Journal of Operational Research, 146(3), 498-516.