Algorithms for a bounded-width order acceptance and scheduling problem with sequence-dependent setup time using decision diagrams

Abstract

Order acceptance and scheduling problems (OAS) is a category of problems where the decision of which jobs to schedule and how to schedule them is intertwined. Decision diagrams have in recent years become a popular method of finding bounds for scheduling problems. However, their use in problems where orders can also be rejected has not yet been explored. We investigate the application of decision diagrams to OAS problems by studying a specific problem in detail. The OAS problem considered here is a single machine deterministic problem with sequence-dependent setup time (OAS-SMS) with a further width restriction such that the number of jobs available to be scheduled at any one time is bound by a constant.

We show this problem to be weakly NP-hard and develop an exact decision diagram formulation for it as well as a restricted decision diagram formulation which we show to be a fully polynomial time approximation scheme (FPTAS) of this problem for a constant width. To make decision diagrams work with order acceptance we generalise the decision diagrams to not require explicit layers associated with the decision variables. We also show that this definition of width used here generalises the Balas-Simonetti neighbourhood in travelling salesman problems and that the exact algorithm solves it in the same worst case time complexity. We evaluate the exact and approximation algorithms on an existing OAS-SMS benchmark set and show it exceeds the state of the art on instances of bounded width.