Customer Order Scheduling To Minimize Total Completion Times

With the development of make-to-order and mass customization, customer orderscheduling problems become the new field of scheduling research. These problemsconsider the case in which there are a set of customer orders consisting of one or moreproducts and the completion time of each order depends on the last-finished products.The Characteristics make scheduling problems a decision-making process to deal withmultiple associated tasks instead of separate products. The idea of customer orderscheduling problems comes from production environment in real life, whichstrengthens the practical background and study value.The customer order scheduling problems contains simple case with singlemachine and complicated cases with multiple machines, which can be further dividedinto dedicated machine case and flexible machines cases. For the case with singlemachine, the customer order scheduling related with total completion time is similarto with multi-stage production. Considering the extra adjusting time between productfrom different types, we take setup time into the set of constrains. For the cases withmultiple machines, most of order scheduling problems have been proved to beNP-hard, in other words, where there exists no polynomial-time solvable algorithm toget the exact solution of these problems.In this dissertation, we researched the problem complexity, mining the specialstructure of the problems. A polynomial-time solvable algorithm was designed for thesingle machine cases. Five Heuristic algorithms were developed to get the up-boundof the problems with multiple dedicated machines, based on that the taboo searchalgorithm was improved to explore better solutions. A two-stage algorithm wasproposed to solve the customer order scheduling with multiple flexible machines. Allof these algorithms are tested by Instances and were proved to be effective andefficient.