Some Research On Inverse Single Machine Scheduling Problem With Minimizing The Total Completion Time

With the inverse optimization problems getting more and more attention in the field of combinatorial optimization,many problems in combinatorial optimiza-tion,such as the minimum spanning tree problem,the shortest path problem,the maximum flow problem,etc,have corresponding inverse problems.But most of the articles discuss the inverse problem under l1,l2,l? distance.Unlike l1,l2,l?,the Hamming distance is a discrete function which makes the inverse problem solution under the Hamming distance is different.We may find appli-cations of the inverse optimization problem under the Hamming distance in real world.In this thesis,we discuss the inverse single machine scheduling problem with minimizing the total completion time under the weighted Hamming distance.Such inverse single machine scheduling problem is aim to modify the parameters of jobs as little as possible to make the given permutation optimal,i.e.,the total completion time is minimum.We discuss two different models:one is to keep the processing time of the jobs unchanged,and adjust the arrival time of the jobs to make the given job sequence optimal.The other is to adjust the processing time of the jobs and keep the arrival time of the jobs unchanged to make the given job sequence optimal.For the first model,we present polynomial time algorithms which can be done in(9(n2 log n)for both the weighted sum-type Hamming distance and the weighted bottleneck-type Hamming distance.For the second model,we first prove that the problem is NP-hard under the weighted sum-type Hamming distance.And,we present an algorithm with a time complexity of O(n2 log n)for the weighted bottleneck-type Hamming distance.