Scheduling Problem With Time-and-position-dependent Effect On Two Machine Environments

In this dissertation,we study a single machine and parallel machines scheduling problems with time and position effects and maintenance restrictions,which parallel machine environment are only involved with the identical machines and unrelated machines.The main results of the dissertation are listed as follows:Single-machine scheduling problems1)We study scheduling problem with time-and-position effect and machine maintenance restriction.Due to the wear and tear of machine,machine will have to maintenanced and the maintenance interval is linearly related to the start time of the job.The objective function are the makespan and total completion time.The proposed problem can be solved in polynomial time by matching algorithm.2)By the group balance principle,the makespan minimum problem can be solved in O(n2 log n),when the actual time of the job is only related with the sum of the actual processing times in the group,and position effect also is related with the job sequence,and the maintenance length is constant.Parallel machines scheduling problems1)We study unrelated machine scheduling problem,which the actual processing time of the job is function of position and time.Objective function is consists of the sum of total completion time?the sum of makespan and the sum of total waiting time.By transferring into assignment problem,the proposed problem can be solved in the O(nk+2/(k-1)!)time.2)We study identical machine scheduling problem,which the actual processing time of the job is function of position and time.Due to the aging machine,machine will have to be reposed.Objective function is consists of the sum of total completion time?the sum of makespan and the sum of total waiting time,By matching algorithm,the proposed problem can be solved in the O((2n+k+nlogn)nk-1/(k-1)!)time.