Bicriteria order acceptance and scheduling with consideration of fill rate

In this paper, we study bicriteria order acceptance and scheduling with consideration of fill rate in a parallel-machine environment. In our scheduling model, either the number of orders being rejected, or the total processing time of the orders being rejected, is not allowed to be greater than a given value, so that a specific constraint of order fill rate is satisfied. We present efficient approximation algorithms with a performance ratio arbitrarily approaching 4/3.