Approximation Scheme for Order Acceptance and Scheduling on a Single Machine with a Reserved Job

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.

KEY WORDS AND PHRASES:

• Scheduling
• approximation scheme
• order acceptance
• reserved job

Disclosure Statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the Humanities and Social Sciences Planning Foundation of the Ministry of Education in China (Grant No. 18YJA630077), and the K.C. Wong Magna Fund in Ningbo University.