Two Kinds Of Scheduling Problems With Varying Processing Times

Scheduling is an important branch of combinatorial optimization, it is widely used in modern industrial applications, such as mechanical manufacturing,computer and so on. In order to be closer to the actual production, the modern scheduling problems continue to break through the classical scheduling model, a job with varying processing times is a kind of modern scheduling problems. This paper studies two kinds of scheduling problems with varying processing time, the contents are summarized as follows:The first chapter introduces the research status and the main work of this paper.In the second chapter we study scheduling problem on a single machine with deteriorating jobs under a deteriorating maintenance consideration. In a certain period of time the machine needs to be maintained to improve the processing speed, and during the period the machine can not process any jobs. Once completing the maintenance, the machine restores the processing efficiency, the deterioration of jobs will start again. The machine maintenance duration is given as a linear nondecreasing function of its starting time. The actual processing time of a job is relevant to its position-specific degradation function. The objective is to find the optimal maintenance position and minimize the makespan. We give some properties of the optimal sequencing for the case with a single machine and prove that under certain conditions,the optimal sequencing is independent with the job scheduling, the optimal policy is to schedule the maintenance activity in the middle of the task sequence.The third chapter deals with multiple common due dates assignment and controllable processing times scheduling problem with both time-dependent deteriorating and position-dependent learning effects, where a maintenance activity is considered. The processing time of a job is a function of its position in a sequence, its starting time, and the amount of a resource allocated to it. The length of the maintenance time is a linear function of its starting time. Once completing the maintenance, the machine restores the processing efficiency, the learning and deterioration of jobs will start again. The objective is to determine the optimal due dates, the optimal location of the maintenance activity, the optimal job sequence,and the optimal resource allocation so as to minimize the sum of earliness,tardiness, due dates and resource related cost. We show that the considered problem can be solved in polynomial time.