A New Formulation for the Single Machine Order Acceptance and Scheduling Problem with Sequence-Dependent Setup Times

Bicakci, Papatya Sevgin; Kara, İmdat

doi:10.22034/2019.2.5

A New Formulation for the Single Machine Order Acceptance and Scheduling Problem with Sequence-Dependent Setup Times

Document Type : Research Paper

Authors

¹ Department of Management, Faculty of Economic and Administrative Sciences, Başkent University, Ankara, Turkey

² Department of Industrial Engineering, Faculty of Engineering, Başkent University, Ankara, Turkey

10.22034/2019.2.5

Abstract

Order acceptance and scheduling problem consists of simultaneously deciding which orders to be selected and how to schedule these selected orders. An extension of this problem was introduced by Oğuz, Salman & Bilgintürk in 2010 and a mathematical formulation was presented. They defined the problem with sequence-dependent setup times and release dates. In this paper, we consider the case where there are no release dates for all orders. We develop a new mathematical formulation with O(n2) binary variables and O(n2) constraints and conduct a detailed computational analysis with CPLEX 12.4 by solving benchmark instances proposed by Cesaret, Oğuz, & Salman (2012). Reduced formulation of Oğuz, Salman & Bilgintürk (2010) can solve the test problems up to 10 orders to optimality in given time limit. Our proposed formulation can solve all the available instances up to 100 orders to optimality within the same time limit. We observe that our formulation is extremely faster than the existing one and can solve small and moderate size real-life problems to optimality.

Keywords

Main Subjects

operations planning,scheduling & control

References

Cesaret, B., Oğuz, C. and Salman, F. S. (2012). A tabu search algorithm for order acceptance and scheduling. Computers & Operations Research, Vol. 39, pp. 1197-1205.

Charnsirisakskul, K., Griffin, P. M. and Keskinocak, P. (2004). Order selection and scheduling with leadtime flexibility. IIE transactions, Vol. 36, pp. 697-707.

Charnsirisakskul, K., Griffin, P. M. and Keskinocak, P. (2006). Pricing and scheduling decisions with leadtime flexibility. European Journal of Operational Research, Vol. 171, pp. 153-169.

Chen, C., Yang, Z., Tan, Y. and He, R. (2014). Diversity controlling genetic algorithm for order acceptance and scheduling problem. Mathematical Problems in Engineering, Vol. 2014, pp. 1-11.

Della Croce, F. (2016). MP or not MP: that is the question. Journal of Scheduling, Vol. 19, pp. 33-42.

Garcia, C. (2016). Resource-constrained scheduling with hard due windows and rejection penalties. Engineering Optimization, Vol. 48, pp. 1515-1528.

Ghosh, J. B. (1997). Job selection in heavily loaded shop. Computers and Operations Research, Vol. 24, pp. 141-145.

Hosteins, P., Cordone, R. and Righini, G. (2016). The Prize-collecting Scheduling Problem with Deadlines. Electronic Notes in Discrete Mathematics, .Vol. 55, pp. 57-60.

Keskinocak, P., Ravi, R. and Tayur, S. (2001). Scheduling and reliable lead-time quotation for orders with availability intervals and lead-time sensitive revenues. Management science, Vol. 47, pp. 264-279.

Keskinocak, P., Ravi, R. and Tayur, S. (1997). Algorithms for reliable lead time quotation. GSIA Working Paper, Carnegie Mellon University, Pittsburgh, PA.

Lewis, H. F. and Slotnick, S. A. (2002). Multi-period job selection: planning workloads to maximize profit. Computers & Operations Research, Vol. 29, pp. 1081-1098.

Lin, S. W. and Ying, K. C. (2013). 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, Vol. 64, pp. 293-311.

Nguyen, S. (2016). A learning and optimizing system for order acceptance and scheduling. The International Journal of Advanced Manufacturing Technology, Vol. 86, pp. 2021-2036.

Nguyen, S., Zhang, M., Johnston, M. and Tan, K. C. (2013). Learning reusable initial solutions for multi-objective order acceptance and scheduling problems with genetic programming. European Conference on Genetic Programming pp. 157-168. Springer, Berlin, Heidelberg.

Nobibon, F. T. and Leus, R. (2011). Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment. Computers & Operations Research, Vol. 38, pp. 367-378.

Oğuz, C., Salman, F. S. and Bilgintürk Yalçın, Z. (2010). Order acceptance and scheduling decisions in make-to-order systems. International Journal of Production Economics, Vol. 125, pp. 200-211.

Reisi-Nafchi, M. and Moslehi, G. (2015). A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem. Applied Soft Computing, Vol. 33, pp. 37-47.

Rom, W. O. and Slotnick, S. A. (2009). Order acceptance using genetic algorithms. Computers & Operations Research, Vol. 36, pp. 1758-1767.

Sarvestani, H. K., Zadeh, A., Seyfi, M. and Rasti-Barzoki, M. (2019). Integrated order acceptance and supply chain scheduling problem with supplier selection and due date assignment. Applied Soft Computing, Vol. 75, pp. 72-83.

Silva, Y. L. T., Subramanian, A. and Pessoa, A. A. (2018). Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times. Computers & Operations Research, Vol. 90, pp. 142-160.

Slotnick, S.A. (2011). Order acceptance and scheduling: A taxonomy and review. European Journal of Operational Research, Vol. 212, pp. 1-11.

Slotnick, S. A. and Morton, T. E. (2007). Order acceptance with weighted tardiness. Computers & Operations Research, Vol. 34, pp. 3029-3042.

Slotnick, S. A. and Morton, T. E. (1996). Selecting jobs for a heavily loaded shop with lateness penalties. Computers & Operations Research, Vol. 23, pp. 131-140.

Stern, H. I. and Avivi, Z. (1990). The selection and scheduling of textile orders. European journal of operational research, Vol. 44, pp. 11-16.

Trigos, F. and López, E. M. (2016). Maximising profit for multiple-product, single-period, single-machine manufacturing under sequential set-up constraints that depend on lot size. International Journal of Production Research, Vol. 54, pp. 1134-1151.

Wang, S. and Ye, B. (2019). Exact methods for order acceptance and scheduling on unrelated parallel machines. Computers and Operations Research, Vol. 104, pp. 159-173.

Wang, X., Zhu, Q. and Cheng, T. C. E. (2015). Subcontracting price schemes for order acceptance and scheduling. Omega, Vol. 54, pp. 1-10.

Wu, GH., Cheng, CY., Yang, HI. and Chena, CT. (2018). An improved water flow-like algorithm for order acceptance and scheduling with identical parallel machines. Applied Soft Computing, Vol. 71, pp. 1072-1084.

Xie, X. and Wang, X. (2016). An enhanced ABC algorithm for single machine order acceptance and scheduling with class setups. Applied Soft Computing, Vol. 44, pp. 255-266.

Yang, B. and Geunes, J. (2007). A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times. Computers & Industrial Engineering, Vol. 53, pp. 420-432.

Yang, B. and Geunes, J. (2003). Heuristic approaches for solving single resource scheduling problems with job-selection flexibility. Department of Industrial & Systems Engineering, University of Florida.

Zandieh, M. and Roumani, M. (2017). A biogeography-based optimization algorithm for order acceptance and scheduling. Journal of Industrial and Production Engineering, Vol. 34, pp. 312-321.