Scheduling Problems With Rejection Jobs And Due Date Assignment

With the development of modern industry, the model of scheduling was brokenthrough continuously. In some scheduling models, If all the jobs aren’t rejected,when a job’s processing time or processing cost is too larger, it will cause thecompletion time bigger or cost too much. Then, a high-level decision has to bemade: schedule only a subset of all the tasks and reject the other ones. If the job isrejected, there is a rejection cost. Every job has a due date. This paper considersthe scheduling problems with rejection jobs and due date assignment. The specificcontent is summarized as follows:1. The actual processing times of jobs are a linear increasing function of theirstart processing times. In this paper, we consider two popular due date assignmentmethods: common due date (CON), equal slack (SLK). For the CON due date ass-ignnment methods, the objective is to find an optimal due date and the processingsequence simultaneously to minimize the total weighted costs for the common duedate assignment, earliness, tardiness and rejection penalties. We reduce the pro-blems to a set of assignment problems, we have shown that the optimal solution canbe obtained in polynomial time. For the SLK due date assignment method, the pro-blem is to find an optimal slack and the processing sequence simultaneously tominimize the total weighted costs for the slack due date assignment, earliness, tardi-ness and rejection penalties. We reduce the problems to a set of assignment pro-blems which can be solved in O(n4)time.2. We analyze the problem with two different processing times functions andthree different due date assignment methods. Resources allocation can be dividedinto linear resource allocation and convex resource allocation. Under the linearresource allocation condition, we consider three due date assignment methods, duedate assignment can be divided into CON (the common due date assignment method),SLK (the slack due date assignment method) and DIF (the unrestricted due dateassignment method), we present polynomial time algorithms to find the optimal jobsequence, due date and resource allocation minimizing the total weighted costs fordue date assignment, earliness, tardiness, resource consumption and rejections pen-alties, respectively. In the condition of convex resource allocation, we also discuss three due date assignment methods, the problem is to find the optimal job sequence,due date and resource allocation simultaneously to minimizing the total weightedcosts for due date assignment, earliness, tardiness, resource consumption and reject-tions penalties, we present the polynomial time algorithms which can be solved inO(n2log n) time.