A Multiple Criteria Genetic Algorithm Scheduling Tool for Production Scheduling in the Capital Goods Industry

Authors

  • Wenbin Xie
  • Chris Hicks
  • Pupong Pongcharoen

Keywords:

genetic algorithms, capital goods, multiple criteria, production scheduling

Abstract

Production planners usually aim to satisfy multiple objectives. This paper describes the development of a genetic algorithm tool that finds optimum trade-offs among delivery performance, resource utilisation, and workin-progress inventory. The tool was specifically developed to meet the requirements of capital goods companies that manufacture products with deep and complex product structures with components that have long and complicated routings. The model takes into account operation and assembly precedence relationships and finite capacity constraints. The tool was tested using various production problems that were obtained from a collaborating company. A series of experiments showed the tool provides a set of non-dominated solutions that enable the planner to choose an optimum trade-off according to their preferences. Previous research had optimised a single objective function. This is the first scheduling tool of its type that has simultaneously optimised delivery performance, resource utilisation and work-in-progress inventory. The quality of the schedules produced was significantly better than the approaches used by the collaborating company.

References

J. Black, N. Hashimzade, and G. Myles. A dictionary of economics 4th edition. Oxford: Oxford University Press, 2009.

N. Rosenberg, “Capital goods, technology and economic growth,” Oxford University Press, Oxford Economic Papers, vol. 15, pp. 217-227, 2003.

C. Hicks and P. M. Braiden, “Computer aided production management issues in the engineer-to-order production of complex capital goods explored using a simulation approach,” International Journal of Production Research, vol. 38, pp. 4783-4810, 2000.

C. Hicks, “Computer aided production management (CAPM) systems in make-to-order / engineer-to-order heavy engineering companies,” Ph.D. dissertation, Faculty of Engineering, University of Newcastle, Newcastle upon Tyne, 1998.

D. Lei, “Multi-objective production scheduling: A survey,” International Journal of Advanced Manufacturing Technology, vol. 43, pp. 925-938, 2009.

D. B. Roman and A. G. del Vallei, “Dynamic assignation of due-dates in an assembly shop based in simulation,” International Journal of Production Research, vol. 34, pp. 1539-1554, June 1, 1996.

J. U. Kim and Y. D. Kim, “Simulated annealing and genetic algorithms for scheduling products with multi-level product structure,” Computers Operations Research, vol. 23, pp. 857-868, 1996.

M. W. Park and Y. D. Kim, “A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints,” European Journal of Operational Research, vol. 123, pp. 504-518, 2000.

P. Pongcharoen, C. Hicks, P. M. Braiden, and D. J. Stewardson, “Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products,” International Journal of Production Economics, vol. 78, pp. 311-322, 2002.

D. E. Goldberg, Genetic algorithms in search, optimisation and machine learning. Reading, MA: Addison-Wesley, 1989.

A. Konak, D. W. Coit, and A. E. Smith, “Multi-objective optimization using genetic algorithms: A tutorial,” Reliability Engineering & System Safety, vol. 91, pp. 992-1007, 2006.

C. A. C. Coello, “An updated survey of GA-based multiobjective optimization techniques,” ACM Computing Surveys, vol. 32, pp. 109-143, 2000.

R. Qing-dao-er-ji, Y. Wang, and X. Wang, “Inventory based two-objective job shop scheduling model and its hybrid genetic algorithm,” Applied Soft Computing, vol. 13, pp. 1400-1406, Mar. 2013.

S. R. Lawrence, “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques,” Carnegie Mellon University, Pittsburgh1984.

Y. K. Lin, J. W. Fowler, and M. E. Pfund, “Multiple-objective heuristics for scheduling unrelated parallel machines,” European Journal of Operational Research, vol. 227, pp. 239-253, June, 2013.

D. Lei, “Multi-objective production scheduling: A survey,” International Journal of Advanced Manufacturing Technology, vol. 43, pp. 926-938, Aug. 2009.

B. A. Wichmann and I. D. Hill, “An efficient and portable pseudo-random number generator,” Applied Statistics, vol. 31, pp. 188-190, 1982.

F. A. Hossen, “Planning risk assessment in the manufacture of complex capital goods,” Ph.D. dissertation, School of Mechanical and Systems Engineering, University of Newcastle upon Tyne, 2006.

I. M. Oliver, D. J. Smith, and J. R. C. Holland, “A study of permutation crossover operators on the traveling salesman problem,” Proceedings of the Second International Conference on Genetic Algorithms, Cambridge, Massachusette, USA, pp. 224-230, 1987.

G. Syswerda, Scheduling optimisation using genetic algorithms. New York: Van Nostrand Reinhold, 1991.

D. E. Goldberg and R. Lingle, “Alleles, loci and the travelling salesman problem,” in First International Conference on Genetic Algorithms and Their Applications, Hilladale, N.J., pp. 154-159, 1985.

T. Murata and H. Ishibuchi, “Performance evaluation of genetic algorithms for flow shop scheduling problems,” Proceedings of the First IEEE International conference on Evolutionary Computation, Orlando, FL, pp. 812-817, 1994.

D. E. Goldberg, Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-wesley, 1989.

P. Pongcharoen, C. Hicks, and P. M. Braiden, “The development of genetic algorithms for the finite capacity scheduling of complex products, with multiple levels of product structure,” European Journal of Operational Research, vol. 152, pp. 215-225, 2004.

W. Xie, C. Hicks, and P. Pongcharoen, “An enhanced single-objective genetic algorithm scheduling tool for solving very large scheduling problems in capital goods industry,” in 16th International Working Seminar on Production Economics, Innsbruck, Austria, pp. 151-169, 2010.

C. M. Fonseca and P. J. Fleming, “Genetic algorithms for multiobjective optimization: formulation, discussion and generalization,” Proceedings of the Fifth International Conference on Genetic Algorithms, Illinois, pp. 416-423, 1993.

K. Deb, Multi-objective optimization using evolutionary algorithms. Chichester: John Wiley & Sons, LTD, 2004.

T. Tunnukij and C. Hicks, “An enhanced grouping genetic algorithm for solving the cell formation problem,” International Journal of Production Research, vol. 47, pp. 1989-2007, 2009.

C. R. Reeves, “Genetic algorithm for flowshop sequencing,” Computers and Operations Research, vol. 22, pp. 5-13, 1995.

D. C. Montgomery, Design and analysis of experiments, 8th ed. New York: John Wiley & Sons, 2012.

W. Xie, “Metaheuristics for single and multiple objectives production scheduling for the capital goods industry,” Ph.D. dissertation, Newcastle University Business School, Newcastle University, 2011.

P. Pongcharoen, D. J. Stewardson, C. Hicks, and P. M. Braiden, “Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry,” Journal of Applied Statistics, vol. 28, pp. 441-455, 2001.

I. M. Oliver, C. J. Smith, and J. R. C. Holland, “A study of permutation crossover on the travelling salesmen problem, ” Proceeding of the Second International Conference on Genetic Algorithms and Their Applications, pp. 225-230, 1987.

T. Tunnukij, “An enhanced grouping genetic algorithm for optimising the formation of design teams and manufacturing cells,” Ph.D. dessertation, Newcastle University Business School, Newcastle University, U.K., 2008.

Downloads

Published

2014-01-01

How to Cite

[1]
W. Xie, C. Hicks, and P. Pongcharoen, “A Multiple Criteria Genetic Algorithm Scheduling Tool for Production Scheduling in the Capital Goods Industry”, Int. j. eng. technol. innov., vol. 4, no. 1, pp. 18–29, Jan. 2014.

Issue

Section

Articles