Several Scheduling Problems With Due Date Assignments

Scheduling problem is an applied science, it has a broad practical background. It is mainly produced in the machinery manufacturing and came to be widely used in many fields, for instance in engineering technology, transportation and computer science. With the development of modern industry, new scheduling models appear continuously. In some scheduling models, a job completed before its due date needs to be saved and results in a cost; completed after its due date has to be paid a consumption penalty. Due date assignment is an important problem. This paper considers three due date assignment problems. The specific content is summarized as follows:1. We consider a common due-window assignment problem. Job processing times are defined by functions of their positions in the sequence,resource allocation, position of the maintenance activity and starting times. The objective is to determine the optimal sequence of jobs, the optimal resource allocation,the optimal position of the maintenance activity and the optimal due-window location, due-window size to minimize a total cost based on earliness, tardiness, resource consumption,due-window size and due-window location. We reduce the problem to a set of assignment problem which can be solved in ()4n O time.2. This paper deals with the single machine multiple due windows assignment and scheduling problems with deterioration effect. We examine two models of the objective function. The first function is a total penalty function containing earliness, tardiness, the makespan costs,due date windows location and size. The second function is a total penalty function containing earliness, tardiness, total completion time costs,due date windows location and size. The objective is to determine the optimal due-windows location, due-windows size, the set of jobs assigned to each due window and the optimal sequence of jobs to minimize the total costs. We formulate the problem as a assignment problem and show that the problem can be solved in)(3n O time.3. We study a single machine scheduling problem with job rejection and multiple common due dates assignment. The objective is to determine the optimal due dates, the set of jobs assigned to each due date and the optimal sequence of jobs to minimize a total cost based on earliness, tardiness, multiple common due dates and rejection cost. We show that the problem is solvable in polynomial time.