Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment |
| |
Authors: | Fabrice Talla Nobibon Roel Leus |
| |
Affiliation: | Research group ORSTAT, Faculty of Business and Economics, K.U. Leuven, Naamsestraat 69, B-3000 Leuven, Belgium |
| |
Abstract: | This paper studies a generalization of the order acceptance and scheduling problem in a single-machine environment where a pool consisting of firm planned orders as well as potential orders is available from which an over-demanded company can select. The capacity available for processing the accepted orders is limited and each order is characterized by a known processing time, delivery date, revenue and a weight representing a penalty per unit-time delay beyond the delivery date. We prove that the existence of a constant-factor approximation algorithm for this problem is unlikely. We propose two linear formulations that are solved using an IP solver and we devise two exact branch-and-bound procedures able to solve instances with up to 50 jobs within reasonable CPU times. We compare the efficiency and quality of the results obtained using the different solution approaches. |
| |
Keywords: | Order acceptance Scheduling Single machine Integer programming Branch-and-bound Firm planned orders |
本文献已被 ScienceDirect 等数据库收录! |