Research On Several Order Acceptance And Scheduling Problems And Optimization Methords

Faced with numerous orders and their distinct due date requirements,how to make order acceptance decision and scheduling decision simultaneously under the situation of limited production capacity to maximize the total net revenue is an important problem of the enterprise.In practice,order acceptance decisioin and scheduling decision are often made separately by the sales department and the production department,respectively.Nat-urally the sales department tends to maximize sale revenues by accepting as many orders as possible,while production department seeks to improve productivity of enterprise by utilizing the production capacity efficiently.Although these two departments could make some communication and coordiration,such inter-departmental conflict of interest as well as the lack of support on optimization theory and method may result in delay in order de-livery,reduced net revenue and even loss of customers,which is difficult to achieve the global optimization objective of the enterprise.Therefore,the research on order acceptance and scheduling problem,which should simultaneously determine which orders to accept and how to schedule them to maximize the total net revenue,has the important theoretical and practical significance.In view of the practical operation management requirements of enterprise,several op-timization decision models for the order acceptance and scheduling problem are estab-lished for the first time.In these models,several decision-making scenarios are taken into account,which include the situation where the orders are partitioned into classes,the two-stage flowshop environment,and the situation where the subcontracting strategy is considered.Faced with various kinds of contraints and highly complex construction,the above optimization models are NP-hard from a complexity point of view.Therefore,it is also the emphasis of this thesis to design the simple and efficient optimazition methods for solving the optimization models presented above respectively.Specifically,the main re-search contents of this thesis are as follow:(1)To solve the single machine order acceptance and scheduling problem with dead-lines and class setups,an enhanced artificial bee colony algorithm is proposed.In this problem,the customer orders are partitioned into classes.Considering this characteristic,the conception of batch is introduced to design the neighborhood operators of the artificial bee colony algorithm.Then,a series of modifications is adopted to improve the performace of the artificial bee colony algorithm,which include using two heuristic algorithms to gen-erate the initial food sources with a high level of quality,applying a self-adaptive selecting strategy to perform the neighborhood search,utilizing a local search approach to balance global exploration and local exploitation,altering the abandoning mode for onlookers for keeping the food source which has the better fitness.Finally,the extensive experimental results indicate that the enhanced artificial bee colony algorithm is both computationally efficient and effective for large sized problem instances.(2)To solve the single machine order acceptance and scheduling problem with tardi-ness penalties and class setups,a Lagrangian relaxation heuristic algorithm is proposed.The Lagrangian relaxed problem is contructed through relaxing the order constraints,and the constraints on forbidden duplication of successive orders is embedded to improve the relaxation solution.A dynamic programming method is then applied to solve the relaxation problem,and the sub-gradient algorithm is used to perform the iteration process of La-grangian multipliers.After that,based on the heuristic informations obtained from relaxa-tion solution,a heuristic combined with optimal properties is designed to contruct the fea-sible solution.A series of computational experiments is performed through extensive ran-domly generated instances,and the experimental results show that the proposed Lagrangi-an relaxation heuristic is able to generate satisfactory near-optimal solutions for large sized problem instances within a reasonable time period.(3)To solve the order acceptance and scheduling problem in two-stage flowshop,a branch and bound algorithm based on depth-first search is proposed.Compared with the breadth-first search,depth-first could generate a feasible solution more quickly.Based on the structure characteristics and properties of two-stage flowshop,the effective heuristic algorithms and relaxation algorithms are developed to generate the lower bounds and upper bounds,respectively.We present dominance rules and use these lower bounds as well as upper bounds obtained for pruning.The computational results indicate that proposed branch and bound algorithm is able to obtain the optimal solutions for instances with up to 20 orders within a reasonable time period.(4)To solve the order acceptance and scheduling problem with subcontracting option,a migrating birds optimization algorithm is proposed in this thesis.Based on heuristic rules and Lagrangian relaxation respectively,two heuristic algorithms are adopted to guarantee the quality of the initial population.To perform the neighborhood search,the destruction and construction operators of iterated greedy algorithm are applied.Then,a local search algorithm is introduced to balance the global exploration and local exploitation.Through the computational experiments on extensive randomly generated instances,the effective-ness of the migrating birds optimization algorithm is verified for solving large sized prob-lem instances.Finally,this thesis also discusses some challenging topics which deserve further re-search in the future based on the above research results.