Bicriteria scheduling problems involving job rejection, controllable processing times and rate-modifying activity

Abstract

This paper addresses the bicriteria scheduling problems with simultaneous consideration of job rejection, controllable processing times and rate-modifying activity on a single machine. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The rate-modifying activity is an activity on the machine that changes the processing times of the jobs scheduled after the activity. The processing time of a job scheduled after the rate-modifying activity decreases with a job-dependent factor. The processing time of each job can also be controlled by allocating extra resource which is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the rejected job set, the accepted job sequence, the time (location) of the rate-modifying activity and the resource allocation that jointly find the trade-off between two criteria, where the first criterion is measured as the sum of total completion time and resource consumption cost while the second criterion is the total rejection cost. We consider four different models for treating the two criteria. The computational complexity status and solution procedures are provided for the problems under consideration.

Keywords:

• scheduling
• job rejection
• controllable processing times
• rate-modifying activity

Acknowledgements

We thank the Editor, an Associate Editor, and anonymous referees for their many helpful comments on earlier versions of our paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This paper was supported in part by the National Natural Science Foundation of China [grant number 71501024], [grant number 11561036], [grant number 71471057]; in part by the Fundamental Research Funds for the Central Universities [DUT15QY32]; in part by the Personnel Training Fund of Kunming University of Science and Technology [grant number KKSY201407098].