Single-machine Scheduling Problems With Position-dependent Effect

Scheduling problem is an important branch of combinatorial optimization problem, it’s originated from the machine manufacturing industry, now it has gradually developed into operational research, system science, control science, management science and com-puter science, and other interdisciplinary fields. In the classical scheduling problems, usually assume that processing time of a job is constant. But in many practical problems, the actual processing time of a job may be dependent on its starts time, location, and allocated resources. This paper mainly considers single machine scheduling problems with position-dependent effect. The main contents are arranged as following:1. Single-machine scheduling problem with a linear positional deterioration effect and maintenance interval.(1)The actual processing time of job is linearly related to its position and the main-tenance interval is linearly related to the total processing time of all jobs scheduled in the former group. We focus on minimizing two classical objectives:the makespan and the total completion times. We prove that group balance principle is satisfied under the makespan.(2)For the total completion time problem, we can convert this problem into linear assignment problem, and proved that the problem is solvable in polynomial time, the time complexity is O(nk0+3).2. Single-machine group scheduling problem with position-dependent processing times and ready times.(1)We consider the group-dependent job-independent positional effect, and the setup time is linearly related to the completion time of the former group under certain condi-tions. The actual processing time of the job is the function of the position factors. The actual setup time of the group is a linear function of the completion time of the former group. Before starting the processing, the grouping of jobs have been confirmed. The decision should be taken regarding possible sequences of jobs in each group and the order between groups to minimize the makespan.(2) We also showed that the special case of these problem can be solved in polynomial time and deduced the relevant conclusions and algorithms.3. Single-machine scheduling problem with past-sequence-dependent setup times and a general learning effect.(1)The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent(p-s-d). The actual processing time of a job is not only a function of the sum of the logarithm of the processing times of the jobs already processed, but also a function of the job’s scheduled position. We show that the makespan minimization problem, the total completion time minimization problem can be solved in polynomial time, respectively.(2)Under certain conditions, it is also showed that the problems to minimize the total weighted completion time and the maximum lateness are polynomially solvable.