LAUSR

SYNOPTIC ABSTRACT In this article, an order acceptance and scheduling problem on a single machine with a reserved job is investigated. In this problem, a set of orders/jobs is possible to be processed on a single machine subject to a given time interval for processing an extra reserved job. Each job in the given set is either accepted to process or rejected by paying its corresponding penalty. The task is to choose some jobs to be accepted and schedule them with the goal of minimizing the sum of weighted completion times of the accepted jobs and the penalties of the rejected jobs. A pseudo-polynomial time exact algorithm by dynamic programming is proposed. Furthermore, based on the dynamic programming exact algorithm, a fully polynomial time approximation scheme is designed by applying the sparsing technique.