Models And Algorithems For Orders Sequencing And Scheduling In The Make-to-Order Environment

With the rapid development of economy and the fast improvement of people's standard of living,customers demand exhibits characteristics of personalization and diversity.This is reflected in two aspects:(1)customers prefer to personalized products or service;(2)customers require prompt response to their need.In order to provide customers with customized products,and compete in market effectively,the business strategy used by firms has been transferred from MTS(make-to-stock)to MTO(make-to-order).Under MTO business model,customer orders are usually different,hence it is difficult for firms to keep inventory to meet possible customer demand.Addition,firms are often faced with limited capacity,thus firms can not satisfy all customer needs promptly.As a result,for firms operating in MTO business model,the key to win market share in competitive market is to satisfy customer needs with minimum cost and shortest time under the limited capacity constraint.Academic research and management practice proves that dynamic pricing and due date quotation are effective tools to satisfy customer needs with minimum cost and shortest time under the limited capacity constraint.For firms operating in MTO business model,in order to satisfy customization needs from customers with limited capacity,it is necessary to consider orders management and orders scheduling jointly.This dissertation studies orders management and scheduling problems for firms in MTO environment from the angle of dynamic pricing and due date quotation.Therefore,this dissertation consists of two parts:(1)study joint dynamic pricing and orders scheduling problems;(2)studying integrated due date quotation and order scheduling problems.Two research problems with different orders acceptance and processing requirements are studied in the first part.Three research problems are studied in the second part,and these three problems can be devided into two classes.Specifically,the due date is a point in the first class,while the due date is an interval in the second class.In this dissertation,theoretical analysis method and computational experiment analysis method are applied.The theoretical analysis is to analyze properties of problems and models,and provide theoretical basis for designing effective algorithms to solve problems.Computational experiment analysis is to provide data proofs for evaluating performance of proposed algorithms and achieve some management insights to supervise management practice.The main research content and results in this dissertation are concluded as follows:1.Study joint dynamic pricing and order scheduling problems.In the problem,a firm produces a number of customized products from a base product over a planning horizon.At the beginning of each period,the firm selects a price from multiple available prices to set the price of the base product,based on which the price for each customized product is set accordingly.Then,the firm processes accepted orders of all the products on a single production line,so as to maximize total profit or total revenue over the given planning horizon.Two specific problems with different order acceptance and processing requirements are studied.In the first problem,the firm has to accept all incoming orders but is allowed to complete some orders after their due dates with tardiness penalties.In the second problem,the firm can reject some incoming orders,but must complete processing all accepted orders by their due dates.For the two problems,this dissertation first analyzes their time complexity and proves that both of them are NP-hard problem,and then proposes dynamic programming(DP)algorithm,full polynomial time approximation scheme(FPTAS)and heuristic algorithms to solve the problems.Finally,this dissertation conducts series of computational experiment.Studies show that:(1)compared with constant pricing,dynamic pricing is an effective tool to improve firm performance;(2)simple pricing rules often have good performance;(3)the number of available prices influence the net revenue that the firm can obtain,but as the number of available prices increases,the gains of firms tend to be stable.2.Study order scheduling problems with due date quotation,controllable processing time and processing deadline.In the problem,a firm decides due dates of orders with CON due date assignment method and processes orders on a single production line.In process of orders production,the firm has to make sure that all orders are completed by a given deadline,but the firm can change orders processing time by allocating additional resource.The objective is to minimize the total cost for earliness,tardiness,due date quotation and resource consumption.For the problem,this dissertation first establishes scheduling models,analyzes its time complexity and proves that it is NP-hard.Then,this dissertation identifies several special cases that can be solved in polynomial time.And finally this dissertation provides algorithms to solve the problem,including branch and bound algorithm and Tabu search,and conducts computational experiment for different problem size.Studies show that:(1)the introduction of processing deadline makes the problem be more complicated;(2)the way of neighborhood generation is a key factor that affects the performance of Tabu search;and(3)for small size problem,Tabu search can achieve good performance.3.Study order scheduling problems with orders placement probability,which is determined by quoted due date.In the problem,a firm applies the SLK due date assignment method to decide due dates of customer orders,based on quoted due date,customers place orders with certain probability.Then,the firm processes placed orders on its single production line,and processing orders bring benefits.The objective is to maximize total expected profit,and satisfy the constraint that all placed orders must be completed by their due dates.Three problems with different scheduling objective are examined:(1)makespan;(2)total completion time;(3)total earliness.For the three problems,this dissertation first establishes the relationship of quoted due date and orders placement probability and the scheduling models,and then analyzes properties of solutions,and finally provides optimal algorithms to solve these problems.Studies show that:(1)all these three problems are polynomially solvable;(2)the introduction of orders placement probability influence orders processing schedule.4.Study order scheduling problems with due window assignment and deteriorating orders.In the problem,a firm applies CON / SLK / DIF due window assignment methods to decide due dates of orders and processes orders on its single production line.For due window assignment,the earliest due date and the latest due date are decision variables.Addition,in the problem,the actual processing time of an order is linear function of its starting time,and the deteriorating rates of orders are order-dependent.Under each due window assignment model,this dissertation studies two problems with different objectives:(1)minimize the total cost for earliness,tardiness and due window assignment;(2)minimize total cost for number of early orders,number of tardy orders and due window assignment.For each problem,this dissertation first establish scheduling model,and then analyzes properties of optimal solutions,and finally provides algorithms for solving these problems.Studies show that:(1)all these problems are polynomial solvable;(2)the deteriorating rate is the key factor for determining the optimal orders schedule;(3)the type of due window assignment influences the problem analysis process.The innovation of this dissertation is mainly reflected in four aspects.1.This dissertation expands and deepens exist studies on integrated pricing and scheduling problems.Specifically,this dissertation proposes and solves the problem with dynamic pricing and scheduling decisions in multiple periods,obtains optimal algorithm,full polynomial time approximation scheme and heuristic algorithms for pricing and scheduling policy,and reveals relationship between the number of available prices and the solution of the problem.2.This dissertation enriches exist literature on due date quotation and scheduling problems.Specifically,this dissertation considers influence of makespan constraint on solution,finds the fact that makespan constraint changes time complexity of the problem,and proposes optimal algorithm and heuristic algorithms to achieve the optimal due date quotation and orders schedules.3.This dissertation remedies the deficiencies of the previous literatures' assumptions on due date quotation and orders placement.Specifically,this dissertation considers the case that the length of quoted due date affects customer orders placement probability,establishes the relationship between due date quotation and orders placement probability,finds properties of optimal orders schedule,and obtains the optimal due date quotation policy.4.This dissertation supplements the previous studies on due window quotation and deteriorating orders scheduling problems.Specifically,this dissertation considers CON/SLK/DIF due window assignment methods and the case with order-dependent deteriorating rate,reveals the relationship between orders deteriorating rates and orders schedule,finds that the type of due window quotation influence problem analysis process,and proposes polynomial algorithms to solve problems.