Single-machine Serial-batch Delivery Scheduling With Two Competing Agents And Due Date Assignment

The scheduling problem with due date assignment and multi-agent batch delivery problem are developed on the basis of classical scheduling problem.In previous studies,the two issues were studied separately.In the scheduling problem with due date assignment,the due date is usually a constant given in advance,but in many cases,the due date is a variable that requires decision-makers to make decisions according to the actual situation.Batch delivery scheduling problem usually only considers the case of one agent,but ignores the case of multiple competing agents using limited resources in reality.Dissertation mainly studies the single-machine serial-batch delivery scheduling problem with two competing agents and due date assignment.For two competing agents,a batch of continuously processed jobs is formed by the same agent.The batch of jobs are transported to the corresponding agent in time after finishing the processing.Each batch of transportation will incur a certain transportation cost.The completion time of each batch of jobs is equal to the completion time of the last job in that batch.Dissertation mainly explores the optimization objectives(the earliness,tardiness,job holding,due date assignment,and batch delivery costs)that each agent wants to minimize in two schemes of time assignment CON(job has the same due date assignment)and DIF(job has different due date assignment).The overall scheduling objective is to find the optimal scheduling scheme so as to minimize the target value of another agent under the condition that the target value of one agent does not exceed the given value.Dissertation studies three problems in detail.For each problem,it mainly discusses the corresponding NP-hard,design an effective solution algorithm,and analyze the computational complexity of the algorithm.In dissertation,it proves that all three problems studied are NP-hard,and give pseudo-polynomial time optimal algorithm and complete polynomial time approximation scheme.