Abstract
In this study, a decision problem simultaneously considers order acceptance and production scheduling in a non-preemptive single-machine environment is investigated. Given a set of considered jobs whose ready dates, processing times, due dates, deadlines, revenues, and tardiness costs are known parameters, an optimal schedule consists of a subset of considered jobs and specifies the start time of each selected job that maximizes total profits. Three solution methods – mixed integer programming (MIP), an implicit enumeration method (IE), and a branch-and-bound method (B&B) are proposed to solve the problem. To reduce the search space of IE and B&B, this study suggests four dominance rules and three fathom rules which effectively reduce a large number of sub-trees. In B&B, the estimated upper bound of a node in the search tree is obtained by relaxing the sub-problem of the node into an assignment problem, in which the assumption that preemption is not allowed and jobs cannot be divided into several proportions are removed, developed by Slotnick and Morton (2007). According to the relationships between considered jobs’ ready dates and deadlines, a relation providing a partial ordering to the set of considered jobs is suggested. The partial ordering sorts the set of considered jobs into a heuristic sequence, which serves as a branching sequence for IE and B&B, which adopt a depth-first search scheme. The heuristic sequence helps both methods find a better solution in the early stage of computation. The experiment result shows that MIP requires much more time to completely solve a problem than IE and B&B. However, if an optimal solution is not necessary, MIP can provide a good solution more efficiently than IE and B&B. Keywords: Order acceptance and scheduling; Maximizing profit; Branch-and-bound method; Partial ordering