Research On Scheduling Problems With Periodic Due Date

In the scheduling problem research,traditional due date rule specifies that the due date of each job is determined by the job itself,independent of the job's processing sequencing position in the scheduling.However,the reality exists that manufacturing companies rely on the third-party logistics companies to provide vehicles to transport products.Trucks arrive at the manufacturing plant periodically to deliver products to the warehouse according to a time table.The i-th truck arriving at the factory is responsible for transporting the i-th batch of products.If the i-th batch of products is completed before the arrival of the i-th truck,then the manufacturer incurs inventory costs,otherwise the truck incurs waiting costs.If the i-th batch of products is completed exactly when the i-th truck arrives,then no cost is incurred.In this case,the traditional due date rule is not conducive to modeling realistic situations.Therefore,in this thesis,the due date of the job is set to be specified by the processing position of the job in the specific scheduling,and the length of the interval between two consecutive due dates is equal.This due date setting rule is called the periodic due date rule.This thesis study scheduling problems under four different machine environments with periodic due date rule,and the objectives this thesis consider are all to minimize the maximum tardiness.The research content includes the following aspects:(1)Research of the scheduling problem under the single-machine environment with periodic due date rule:Combined with the SPT rule in the scheduling theory,a polynomial-time algorithm with time complexity of O(nlogn)is designed.Meanwhile,computational experiments are conducted to verify the accuracy of theoretical results.(2)Research of the scheduling problem under the two-and m-parallel-machine environment with periodic due date rule:This thesis constructs an instance by using the binary NP-complete Equal-Size Partition problem to prove that the scheduling problem under the two-parallel-machine environment is a binary NP-hard problem and constructs an instance by using the strong NP-complete 3-Partition problem to prove that the scheduling problem under the m-parallel-machine environment is a strong NP-hard problem.In addition,a dynamic programming algorithm with time complexity of O(n·2ⁿ·P/2)is designed to solve the scheduling problem under the two-parallel-machine environment.Computational experiments are conducted to verify the computational efficiency and the accuracy of theoretical results.(3)Research of the scheduling problem under the two-machine flow-shop environment with periodic due date rule:This thesis constructs an instance by using the strong NP-complete3-Partition problem to prove that the scheduling problem under the two-machine flow-shop environment is a strong NP-hard problem.It is also inferred that when the objective function is changed to the total tardiness or the total number of tardy jobs,these two problems are still strong NP-hard.This is an improvement on the research findings.(4)Research of the scheduling problem under the two-machine open-shop environment with periodic due date rule:This thesis constructs an instance by using the strong NP-complete3-Partition problem to prove that the scheduling problem under the two-machine open-shop environment is a strong NP-hard problemThis thesis uses different instance constructions and methods to prove the complexity of the scheduling problem or design algorithms to solve problems.It supplements the research on these scheduling problems in theory.In practical applications,it can help manufacturing companies to grasp their mathematical models in a timely manner when they face similar problems,and thus provide suggestions for their rapid decision making.