Algorithms For Some Scheduling Problems With Variable Processing Times

In some of actual production, some reasons may affect the actual processing time of the job, such as the wear and tear of the machine, the change of the proficiency of workers, the allocation of resources and etc. That is, the actual processing time of a job not only depends on its basic processing time but also depends on its scheduled position, starting time and the amount of a resource allocated to it. At the same time, machines may be unavailable because of preventive maintenances and periodical repairs, namely, the machine availability constraint. The availability constraint in this thesis is nonresumable, that is, one job needs to be restart if the job is not finished before the machine unavailable interval.This thesis considers some scheduling problems with learning and deteriorating effect. For the case with availability constraint, we discuss the scheduling problem with or without rejection, respectively. This thesis also discusses some single machine scheduling problems with multiple maintenances. The content of the dissertation is summarized as follows.1) The actual processing time of a job depends on its basic processing time, its scheduled position and starting time. Moreover the machine has an availability constraint. We consider some scheduling problems with or without rejection, respectively.(1) For the scheduling problems without rejection, we consider single machine and two parallel machines. The objective is to minimize the total completion time. Two pseudo-polynomial dynamic programming algorithms are proposed to solve the above problems, respectively. Specifically, we give a polynomial time optimal algorithm with complexity O(n4) for the two parallel machines scheduling problem, in which one machine is unavailable at time zero and anther is always available. Finally, we give a numerical example to illustrate its calculation process.(2) For the scheduling problems with rejection, we study the single machine and two parallel machines scheduling problems that the objective is to minimize the sum of the total completion time of the accepted jobs and the total penalty of the rejected jobs. Two pseudo-polynomial dynamic programming algorithms are proposed to solve the above problems, respectively.2) The actual processing time of a job depends on its basic processing time, its scheduled position, starting time and the amount of a resource allocated to it. Machines need several maintenances, and the maximum number of maintenance times is given. For the case that the parameter of the learning effect is job-independent, the objectives are to(1) minimize the sum of the makespan and resource related cost and(2) minimize the sum of the total completion time and resource related cost, respectively. Further we research objective function for the sum of the makespan and resource related cost for the case that the parameter of the learning effect is job-dependent. By transforming them into the assignment problems, we can get the optimal solution in polynomial time.