Exact Algorithms Of Several Scheduling Problems In Manufacture And Warehouse Management

In this thesis, we study exact algorithms of several scheduling problems in manu-facture and warehouse management. We first study the single machine total tardiness problem, the flow shop lot splitting problem and the tactical fixed job scheduling prob-lem which come from manufacture industry. We employ branch-and-bound algorithm, lagrangian relaxation algorithm and column generation algorithm to solve these three scheduling problems respectively. We then apply column generation algorithm for a NP-hard order scheduling problem which appears in warehouse management.In chapter2, we deal with the single machine total tardiness problem, and prove that if the job sequences produced by two heuristics, named as Time Forward and Time Backward algorithms, have the same starting and ending job subsequences, then there exists an optimal job sequence with the starting and ending job subsequences. The computation experiments show that there is a significant improvement of the running time of a branch and bound algorithm with the incorporation of the new property. Our algorithm can solve instances with up to800jobs while the latest algorithms can only solve instances with500jobs.In chapter3, we discuss the discrete lot splitting problem with attached setup times in the two-machine flow shop. The objective is to minimize the total flow time. We employ dynamic programming to solve Lagrangian relaxation problems and obtain a pair of lower and upper bounds. We also present a neighborhood search method to improve the upper bound. In the computational test, our algorithm can compute all the40instances and the average gap between the lower bound and the upper bound is only2.1%.In chapter4, we address the tactical fixed job scheduling problem. In this problem, there are different machine classes and job types. For the problem with spread time con-straints, we develop a branch and price algorithm to solve instances with up to300jobs. We further investigate the influence of machine flexibility by computational experiments and the results show that limited machine flexibility is good enough in most situations. In the appendix of this chapter, we present a neighborhood search algorithm which can be embedded into our algorithm and reduce the computational time for some difficult instances.In chapter5, we consider the order scheduling problem in a self-storage warehouse. There are different classes for storage units in this problem and the start time and end time of each order are given. The warehouse operations manager needs to decide which orders to accept and schedule them in different storage units to maximize the revenue. For the problem with upgrading option, we propose a branch and price method. Computational experiments show, compared with current method in self-storage warehouses, our method can significantly improve the revenue up to50%.