Theory Research On Produduction And Logistics Batching Scheduling

In this thesis,we consider integrated scheduling problems of production and logistics that arise in steel industries.From the view of scheduling theory,we add new scheduling models.From the view of practice,reasonable and effective production and logistics schedule can effectively reduce production and logistics costs,holding times of products,and improve the quality of products.For production and logistics scheduling problems,we analyze complexities of various scheduling problems.For easily solvable problems,we present optimal algorithms in polynomial time.For the general cases,we propose NP-hard proofs,design effective approximation algorithms,and evaluate the effectiveness of the algorithms by using worst case analysis and computational experiments.For special cases,we analyze optimality properties and develop effective algorithms.The content is summarized as follows.1)Production Scheduling Problems.(1)A new flowshop scheduling problem of two batch machines with capacity considerations.In this problem,a machine can process only a bounded number of jobs in one batch.Subject to the practical constraint,all the jobs of a batch on the first machine must be assigned to the same batch on the second machine.The problem is to determine the formation of batches and the schedules of these batches on the first and second machines such that makespan is minimized.For the problem,we analyze its computational complexity and present a fast heuristic with worst-case analysis.For each of special cases,we give an efficient exact algorithm to solve the case to optimality.Finally,computational experiments demonstrate that our algorithm is very efficient and effective.(2)Cooperation in a single-machine scheduling problem with job deterioration.In the scheduling problem,all the jobs have to be processed on the single machine,the processing time of each job is an increasing function of its starting times,and the cost of each job hnearly depends on its completion time.Grven an initial order of all the jobs,we define cooperative games corresponding to the scheduling problem.The two questions considered are shown:the first is how to find the maximal cost savings of a coalition,and the second is how to allocate the cost savings obtained by rearranging the jobs optimally in the coalition.These sequencing games are convex.A new cost allocation rule is proposed and proved that it is a core allocation for these sequencing games.2)New Logistics Batching Scheduling.Given a set of jobs,a single crane is available to load jobs,one by one,onto semitrailers with a given capacity.Loaded semitrailers are assigned to tractors for transportation tasks.Subject to limited resources(crane,semitrailers,and tractors),the problem is to determine(1)an assignment of jobs to semitrailers for loading tasks,(2)a sequence for the crane to load jobs onto semitrailers,(3)an assignment of loaded semitrailers to tractors for transportation tasks,and(4)a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized.We first formulate the problem as a mixed integer linear programming model(MILPM)and prove that the problem is strongly NP-hard.Then,optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms.We develop a constructive heuristic and a recovering beam search heuristic to solve this problem.Furthermore,two branch-and-bound algorithms with two different lower bounds are developed to solve the problem to optimality.Finally,computational experiments using both real data and randomly generated data demonstrate that our algorithms are highly efficient and effective.3)Integrated Production and Delivery Scheduling Problems.(1)Integrated production and two-stage delivery scheduling of make-to-order products.In the problem,make-to-order products are first processed in a plant,then delivered to the customer sites through two shipping stages:first from the plant to a pool point(e.g.port,distribution or consolidation center),and then from the pool point to customer sites.The objective is to find a joint schedule of job processing at the plant and two-stage shipping of completed jobs to the customer sites,so as to optimize a performance measure that takes into account both delivery timeliness and total transportation cost.We consider two problems where delivery timeliness is measured by total or maximum lead time of the jobs and one problem where delivery timeliness is measured by total tardiness of the jobs.For all the problems with a single production line at the plant,we provide optimal dynamic programming algorithms.For the more general problems with multiple production lines at the plant,we propose fast heuristics and analyze their worst-case and asymptotic performance.Computational experiments using real data from a plant demonstrate that our heuristics generate better solutions than their rule-based approaches for their integrated steel coil production and delivery scheduling problems.By comparing to lower bounds using randomly generated test instances,it is also shown that our heuristics are capable of generating near optimal solutions quickly.(2)Integrated production,inventory and delivery problem.In the problem,customer orders have pre-specified delivery time windows and are first processed in a plant and then delivered to the customers by transporters which have fixed delivery departure times.If an order is completed but not immediately delivered by a transporter,the order is kept temporarily in inventory,which incurs an inventory cost.There is a delivery cost for delivering an order,which varies with the departure time.Given a set of orders,the objective is to find an integrated schedule for processing the orders,keeping finished orders in inventory if necessary,and delivering them to the customers such that the total inventory and delivery cost is minimum.We consider two classes of problems including problems where order delivery is splittable and problems where order delivery is non-splittable.For each of the problems considered,we study its computational complexity by either showing that the problem is NP-hard or proposing an algorithm that can find an optimal solution.For the two most general problems,we show that any polynomial time algorithm has an arbitrarily bad worst-case performance bound,and propose column generation based heuristic algorithms that can find near optimal solutions for them in a reasonable computational time.