SpringerLink
Log in

A learning and optimizing system for order acceptance and scheduling

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

Order acceptance and scheduling is an interesting scheduling problem when scheduling and acceptance decisions need to be handled simultaneously. The complexity of the problem causes difficulty for many solution methods. In this paper, we proposed a learning and optimizing system to deal with the order acceptance and scheduling problem with a single-machine and dependent setup times. The aim of this system is to combine the advantages of the hyper-heuristic for learning useful scheduling rules and the meta-heuristic for further refining the solutions from the obtained rules. The experiments show that the proposed system is very effective as compared to other heuristics proposed in the literature. The analyses also show the benefits of scheduling rules obtained by the hyper-heuristic, especially for large-scale problem instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Allahverdi A, Gupta JN, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27(2):219–239

    Article  Google Scholar 

  2. Altendorfer K, Minner S (2015) Influence of order acceptance policies on optimal capacity investment with stochastic customer required lead times. Eur J Oper Res 243(2):555–565

    Article  MathSciNet  MATH  Google Scholar 

  3. Branke J, Hildebrandt T, Scholz-Reiter B (2014) Hyper-heuristic evolution of dispatching rules: a comparison of rule representations. Evol Comput. In press. doi:10.1162/EVCO_a_00131

  4. Branke J, Nguyen S, Pickardt C, Zhang M (2015) Automated design of production scheduling heuristics: a review. IEEE Trans Evolut Comput. doi:10.1109/TEVC.2015.2429314

  5. Burke E, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward J (2009) Exploring hyper-heuristic methodologies with genetic programming. In: Mumford C, Jain L (eds) Computational intelligence, intelligent systems reference library, vol 1. Springer, Berlin Heidelberg, pp 177–201

  6. Burke EK, Hyde M, Kendall G, Woodward J (2007) Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one. In: Lipson H, Thierens D (eds) GECCO ’07: proceedings of the 9th annual conference on genetic and evolutionary computation. ACM Press, New York, pp 1559–1565

  7. Cesaret B, Oguz C, Salman FS (2012) A tabu search algorithm for order acceptance and scheduling. Comput Oper Res 39(6):1197–1205

    Article  Google Scholar 

  8. Choobineh FF, Mohebbi E, Khoo H (2006) A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times. Eur J Oper Res 175(1):318–337

    Article  MATH  Google Scholar 

  9. Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Article  Google Scholar 

  10. Eguchi T, Oba F, Toyooka S (2008) A robust scheduling rule using a neural network in dynamically changing job-shop environments. Int J Manuf Technol Manag 14(3–4):266–288

    Google Scholar 

  11. El-Bouri A, Balakrishnan S, Popplewell N (2000) Sequencing jobs on a single machine: a neural network approach. Eur J Oper Res 126(3):474–490

    Article  MathSciNet  MATH  Google Scholar 

  12. Geiger CD, Uzsoy R, Aytuġ H (2006) Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. J Sched 9(1):7–34

    Article  MATH  Google Scholar 

  13. Gen M, Cheng R (1996) Genetic algorithms and manufacturing systems design, 1st edn. Wiley

  14. Ghosh JB (1997) Job selection in a heavily loaded shop. Comput Oper Res 24(2):141–145

    Article  MathSciNet  MATH  Google Scholar 

  15. Giffler B, Thompson GL (1960) Algorithms for solving production-scheduling problems. Oper Res 8 (4):487–503

    Article  MathSciNet  MATH  Google Scholar 

  16. Hildebrandt T, Heger J, Scholz-Reiter B (2010) Towards improved dispatching rules for complex shop floor scenarios: a genetic programming approach. In: GECCO’10: proceedings of the 12th annual conference on genetic and evolutionary computation, pp 257–264

  17. Huang S, Lu M, Wan G (2011) Integrated order selection and production scheduling under MTO strategy. Int J Prod Res 49(13):4085–4101

    Article  Google Scholar 

  18. Ingimundardottir H, Runarsson TP (2011) Supervised learning linear priority dispatch rules for job-shop scheduling. In: Coello Coello CA (ed) Learning and intelligent optimization, LNCS, vol 6683. Springer, Berlin and Heidelberg, pp 263– 277

  19. Jakobović D, Budin L (2006) Dynamic scheduling with genetic programming. In: Collet P, Tomassini M, Ebner M, Gustafson S, Ekárt A (eds) Genetic programming, LNCS, vol 3905. Springer, Berlin and Heidelberg, pp 73–84

  20. Kapanoglu M, Alikalfa M (2011) Learning If-THEN priority rules for dynamic job shops using genetic algorithms. Robot Comput-Integrat Manuf 27(1):47–55

    Article  Google Scholar 

  21. Kofler M, Wagner S, Beham A, Kronberger G, Affenzeller M (2009) Priority rule generation with a genetic algorithm to minimize sequence dependent setup costs. In: Moreno-Díaz R, Pichler F, Quesada-Arencibia A (eds) Computer aided systems theory — EUROCAST 2009, LNCS, vol 5717. Springer, Berlin and Heidelberg, pp 817–824

  22. Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, Cambridge

  23. Li X, Olafsson S (2005) Discovering dispatching rules using data mining. J Sched 8(6):515–527

    Article  MathSciNet  MATH  Google Scholar 

  24. Mestry S, Damodaran P, Chen CS (2011) A branch and price solution approach for order acceptance and capacity planning in make-to-order operations. Eur J Oper Res 211(3):480– 495

    Article  MathSciNet  MATH  Google Scholar 

  25. Miyashita K (2000) Job-shop scheduling with GP. In: GECCO’00: proceedings of the genetic and evolutionary computation conference, pp 505–512

  26. Nguyen S, Zhang M, Johnston M (2014a) A sequential genetic programming method to learn forward construction heuristics for order acceptance and scheduling. In: 2014 IEEE congress on evolutionary computation (CEC), pp 1824–1831

  27. Nguyen S, Zhang M, Johnston M (2014b) A sequential genetic programming method to learn forward construction heuristics for order acceptance and scheduling. In: Liu D, Hussain A, Zeng Z, Zhang N (eds) 2014 IEEE congress on evolutionary computation (CEC). IEEE Press, Piscataway, pp 1824–1831

  28. Nguyen S, Zhang M, Johnston M, Tan KC (2013a) A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Trans Evol Comput 17 (5):621–639

    Article  Google Scholar 

  29. Nguyen S, Zhang M, Johnston M, Tan KC (2013b) Learning reusable initial solutions for multi-objective order acceptance and scheduling problems with genetic programming. In: Krawiec K, Moraglio A, Hu T, Etaner-Uyar Ai, Hu B (eds) Genetic programming, vol 7831. Springer, Berlin Heidelberg, pp 157– 168

  30. Nguyen S, Zhang M, Johnston M, Tan KC (2013c) Learning reusable initial solutions for multi-objective order acceptance and scheduling problems with genetic programming. In: Krawiec K, Moraglio A, Hu T, Etaner-Uyar AṠ, Hu B (eds) Genetic programming, LNCS, vol 7831. Springer, Berlin and Heidelberg, pp 157–168

  31. Nguyen S, Zhang M, Johnston M, Tan KC (2014c) Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming. IEEE Trans Evol Comput 18 (2):193–208

    Article  Google Scholar 

  32. Nie L, Gao L, Li P, Li X (2013) A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates. J Intell Manuf 24(4):763–774

    Article  Google Scholar 

  33. Oguz C, Sibel Salman F, Bilginturk Yalcin Z (2010) Order acceptance and scheduling decisions in make-to-order systems. Int J Prod Econ 125(1):200–211

    Article  Google Scholar 

  34. Park J, Nguyen S, Johnston M, Zhang M (2013a) Evolving stochastic dispatching rules for order acceptance and scheduling via genetic programming. In: AI 2013: advances in artificial intelligence, vol 8272. Springer International Publishing, pp 478–489

  35. Park J, Nguyen S, Zhang M, Johnston M (2013b) Genetic programming for order acceptance and scheduling. In: 2013 IEEE congress on evolutionary computation (CEC), pp 1005–1012

  36. Pinedo ML (2008) Scheduling: theory, algorithms, and systems, 3rd edn. Springer

  37. Piya S (2015) Dealing with customers enquiries simultaneously under contingent situation. Int J Ind Eng Comput 6(3):391–404

    Google Scholar 

  38. Rom WO, Slotnick SA (2009) Order acceptance using genetic algorithms. Comput Oper Res 36(6):1758–1767

    Article  MATH  Google Scholar 

  39. Romagnoli G (2015) Design and simulation of CONWIP in the complex flexible job shop of a Make-To-Order manufacturing firm. Int J Ind Eng Comput 6(1):117–134

    MathSciNet  Google Scholar 

  40. Roundy R, Chen D, Chen P, Cakanyildirim M, Freimer MB, Melkonian V (2005) Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: models and algorithms. IIE Trans 37 (12):1093–1105

    Article  Google Scholar 

  41. Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212(1):1–11

    Article  MathSciNet  Google Scholar 

  42. Slotnick SA, Morton TE (1996) Selecting jobs for a heavily loaded shop with lateness penalties. Comput Oper Res 23(2):131–140

    Article  MATH  Google Scholar 

  43. Slotnick SA, Morton TE (2007) Order acceptance with weighted tardiness. Comput Oper Res 34 (10):3029–3042

    Article  MATH  Google Scholar 

  44. Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54(3):453–473

    Article  Google Scholar 

  45. Thevenin S, Zufferey N, Widmer M (2015) Metaheuristics for a scheduling problem with rejection and tardiness penalties. J Sched 18(1):89–105

    Article  MathSciNet  MATH  Google Scholar 

  46. Tunali S, Ozfirat PM, Ay G (2011) Setting order promising times in a supply chain network using hybrid simulation-analytical approach: an industrial case study. Simul Modell Pract Theory 19(9):1967–1982

    Article  Google Scholar 

  47. Wang X, Cheng T (2015) A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint. Int J Prod Econ 161:74–82

    Article  Google Scholar 

  48. Wang X, **e X, Cheng T (2012a) A modified artificial bee colony algorithm for order acceptance in two-machine flow shops. Int J Prod Econ. doi:10.1016/j.ijpe.2012.06.003

  49. Wang X, **e X, Cheng T (2012b) Order acceptance and scheduling in a two-machine flowshop. Int J Prod Econ. doi:10.1016/j.ijpe.2012.08.020

  50. Wang X, Zhu Q, Cheng T (2015) Subcontracting price schemes for order acceptance and scheduling. Omega 54:1–10

    Article  Google Scholar 

  51. Wester FAW, Wijngaard J, Zijm WRM (1992) Order acceptance strategies in a production-to-order environment with setup times and due-dates. Int J Prod Res 30(6):1313–1326

    Article  MATH  Google Scholar 

  52. Xu L, Wang Q, Huang S (2015) Dynamic order acceptance and scheduling problem with sequence-dependent setup time. Int J Prod Res 53(19):5797–5808. doi:10.1080/00207543.2015.1005768

    Article  Google Scholar 

  53. Yang WH (1999) Survey of scheduling research involving setup times. Int J Syst Sci 30(2):143–155

    Article  MathSciNet  MATH  Google Scholar 

  54. Zhang J, Zhan ZH, Lin Y, Chen N, Gong YJ, Zhong JH, Chung H, Li Y, Shi YH (2011) Evolutionary computation meets machine learning: a survey. IEEE Comput Intell Mag 6(4):68–75

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Business Administration, Hoa Sen University, Ho Chi Minh, Vietnam

    Su Nguyen

  2. Evolutionary Computation Research Group, Victoria University of Wellington, Wellington, New Zealand

    Su Nguyen

Authors
  1. Su Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Su Nguyen.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nguyen, S. A learning and optimizing system for order acceptance and scheduling. Int J Adv Manuf Technol 86, 2021–2036 (2016). https://doi.org/10.1007/s00170-015-8321-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-015-8321-6

Keywords

Search

Navigation