Abstract
Order acceptance and scheduling (OAS) in make-to-order manufacturing systems is a NP-hard problem for which finding optimal solutions for problem instances can be challenging. Because of this, several heuristic approaches have been proposed in the literature to find near-optimal solutions to OAS. Many previous heuristic approaches are very effective, but require careful design and developing new heuristics can be difficult. Genetic Programming (GP) has been used to generate reusable and efficient heuristics in OAS and shows promising results. However, in terms of solution quality, the evolved heuristics are still less competitive as compared to highly customised heuristics designed by human experts. To overcome these limitations, this paper proposes two new Particle Swarm Optimisation (PSO) approaches to OAS. Afterwards, GP evolved rules are combined with an existing Tabu Search (TS) heuristic and with the proposed PSO algorithms as hybrid approaches to OAS. The experimental results show that these PSO approaches are competitive with effective heuristics such as TS. In addition, TS heuristic greatly benefits from evolved rules, whereas PSO approaches do not benefit.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Oğuz, C., Salman, F.S., Yalçın, Z.B.: Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics 125(1), 200–211 (2010)
Ghosh, J.B.: Job selection in a heavily loaded shop. Computers & Operations Research 24(2), 141–145 (1997)
Cesaret, B., Oğuz, C., Salman, F.S.: A tabu search algorithm for order acceptance and scheduling. Computers & Operations Research 39(6), 1197–1205 (2012)
Rom, W.O., Slotnick, S.A.: Order acceptance using genetic algorithms. Computers & Operations Research 36(6), 1758–1767 (2009)
Lin, S., Ying, K.: Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm. Journal of the Operational Research Society (2), 293–311 (2012)
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press (1992)
Park, J., Nguyen, S., Zhang, M., Johnston, M.: Genetic programming for order acceptance and scheduling. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), vol. 7831, pp. 1005–1012 (2013)
Park, J., Nguyen, S., Johnston, M., Zhang, M.: Evolving stochastic dispatching rules for order acceptance and scheduling via genetic programming. In: Cranefield, S., Nayak, A. (eds.) AI 2013. LNCS, vol. 8272, pp. 478–489. Springer, Heidelberg (2013)
Slotnick, S.A.: Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research 212(1), 1–11 (2011)
Nguyen, S., Zhang, M., Johnston, M., Tan, K.C.: 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.) EuroGP 2013. LNCS, vol. 7831, pp. 157–168. Springer, Heidelberg (2013)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. IEEE (1995)
Rameshkumar, K., Suresh, R., Mohanasundaram, K.: Discrete particle swarm optimization (dpso) algorithm for permutation flowshop scheduling to minimize makespan. In: Wang, L., Chen, K., S. Ong, Y. (eds.) ICNC 2005. LNCS, vol. 3612, pp. 572–581. Springer, Heidelberg (2005)
Ruiz, R., Sttzle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research 177(3), 2033–2049 (2007)
Eberhart, R.C., Shi, Y.: Particle swarm optimization: developments, applications and resources. In: Proceedings of 2001 Congress on Evolutionary Computation, vol. 1, pp. 81–86. IEEE (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Park, J., Nguyen, S., Zhang, M., Johnston, M. (2014). Enhancing Heuristics for Order Acceptance and Scheduling Using Genetic Programming. In: Dick, G., et al. Simulated Evolution and Learning. SEAL 2014. Lecture Notes in Computer Science, vol 8886. Springer, Cham. https://doi.org/10.1007/978-3-319-13563-2_61
Download citation
DOI: https://doi.org/10.1007/978-3-319-13563-2_61
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13562-5
Online ISBN: 978-3-319-13563-2
eBook Packages: Computer ScienceComputer Science (R0)