Font Size: a A A

A Study Of Scheduling With Deadlines And Nonregular Criteria

Posted on:2011-04-09Degree:DoctorType:Dissertation
Country:ChinaCandidate:X L ZhongFull Text:PDF
GTID:1119330332473598Subject:Business management
Abstract/Summary:PDF Full Text Request
Scheduling is a class of important combinational optimization problem. The scheduling problem with deadlines requires that each job have to be completed before or on the given due date, namely no tardiness. It can be seen everywhere in practical application. The earliness means the finished jobs need to stored and lead to extra holding cost unavoidably. This paper mainly consider a series of following scheduling problems with deadlines in the environment of single machine, identical parallel machines and shop respectively, in which the objective function is maximum earliness or total earliness, and we obtain some related results.In single machine environment, we consider the following problems:(1) Minimize maximum earliness. The feasibility is discussed and the optimal algorithm is developed for the feasible problem. (2) Minimize maximum earliness cost and allow job preemption. Two special cases are considered primarily, and then we consider the general case and give an optimal algorithm. (3) Minimize maximum earliness, jobs with arrival times. It is proved strongly NP-hard, and we consider a special case with equal processing time. (4) Minimize maximum earliness, jobs with arrival times and allow job preemption. The feasibility is discussed and the optimal algorithm is developed for the feasible problem. (5) Minimize total earliness, jobs with arrival times and allow job preemption. It is proved NP-complete, and we consider a special case with equal processing time.In identical parallel machines environment, we consider the following two problems: (1) Minimize maximum earliness. Determining the feasibility is proved NP-complete. The complexity of the problem is also proved NP-complete even if identical deadlines. Besides, a special case with equal processing time is considered. (2) Minimize total earliness and allow job preemption. It is proved strongly NP-hard, and then we consider a special case with equal processing time.In flow shop and open shop environment, we consider the double machines problem with equal deadline to minimize the maximum earliness respectively. The feasibility is discussed and the optimal algorithm is developed for the feasible problem.
Keywords/Search Tags:Scheduling, Computational complexity, Algorithm, Deadline, Earliness
PDF Full Text Request
Related items