A preemptive priority queue with preemptions penalty

摘要

Preemption is one of the important features in scheduling problems. When preemption is allowed, a customer can immediately receive the service on the arrival time whenever the server is idle or the preemption is justified. While a customer receives a service, one or more preemptions may occur. The primary objective of this paper is to minimize the average waiting time that all customers spend on the system. We consider some thresholds for the maximum allowed number of preemptions and their times to prevent from having a very long waited customer. A heuristic algorithm is presented for the problem, and the implementation of the proposed approach is demonstrated using some numerical examples. In addition, the performance of the proposed algorithm is compared with another existing algorithm.