Exact Algorithms For Machine Scheduling Problems And Two-dimensional Vector Packing Problems

With the fast development of economic globalization,the competition among enterprises is becoming more and more intense.The efficient resource scheduling has become one of the core competitiveness of a company as the energy crisis becoming increasingly prominent.Production scheduling is a critical problem faced by manufacturers in the daily production.Single machine is the basic production unit in a manufacturing factory.Under the current limited level of mechanical technology and investment funds for purchasing the advanced machines,the technology of machine scheduling plays a key role in improving the capacity of businesses to produce the goods.Packing is a key technology for logistics and transportation companies,which can greatly affect the automation level,loading efficiency and business process specification of logistics and transportation industry.Therefore,in the paper,we focus on the production scheduling and packing problems,and design several effective exact algorithms based on column generation for them.First,we propose a single machine scheduling problem considering deterioration effects and flexible periodic maintenance in the actual production scenarios of manufacturing industry.A branch-and-price(BP)algorithm is developed for the problem.By deriving an upper bound of the number of batches in the optimal solution of the problem,we propose a mixed integer programming model for the problem and reformulate it into a set-partitioning model by Dantzig-Wolfe decomposition.Since the pricing problem can be reduced to the shortest path problem with resource constraints,we design an efficient label-setting algorithm to solve it.In the label-setting algorithm,to accelerate the extension of labels,we develop a label dominance rule based on the characteristics and structure of the price problem.Moreover,we also develop a batch domination rule to reduce the number of variables in the set-partitioning model.The LP relaxation of the restricted master problem may have not the integral optimal solution.To find an integer optimal solution,we design two branching strategies:branching on the number of batches and branching on the forward arc in the shortest path problem.The global upper bound is improved by a constructive heuristic algorithm based on a First Fit(FF)algorithm.To evaluate the performance of our BP algorithm with computational experiments,we randomly generated 1440 instances based on the relevant literature.By comparing several key components in the BP algorithm and analyzing the optimal solution,we prove that the BP algorithm we designed is efficient.We also give an optimal theorem for the online version of the problem.Second,we investigate a two-dimensional vector packing problem with general cost function on volumetric weight.The background of the problem is from a kind of practical packing charge problem in the logistics and transportation industry.We introduce the standard charging process of well-known logistics enterprises.To our best knowledge,this is the first paper to consider the bin packing problem on volumetric weight.To solve the problem,we design a branch-and-price-and-cut(BPC)algorithm by combining branch-and-bound algorithm with additional constraints.Because of the special structure of cost function,the problem we consider is much more complicated than the classical two-dimensional vector packing problem(2DVPP).In order to accelerate the promotion of the global lower bound,we use two valid inequalities:rounding inequalities(RI)and Subset-row inequalities(SRI).As the SRI will change the structure of the pricing problem and make it more complicated,we only add the SRI to the root node.Since the pricing problem can be seen as a shortest path problem,we design a label-setting algorithm to solve it.To reduce the number of labels to extend,we derive a dominance rule to identify labels that can be safely discarded for the pricing problem with the Subset-row inequalities.To obtain the optimal integer solution,we adopt two branching strategies:branching on the number of bins and branching on pairs of items.The upper bound of each node is computed by a shortest path decode.To evaluate the performance of our BPC algorithm,we randomly generate 360 instances based on the related literature.We use CPLEX solver to solve the mixed integer programming model of the problem,and the results are compared with those obtained by our BPC algorithm.The results show that our BPC algorithm is much more efficient than CPLEX.In addition,we also conduct computational experiments on a selected set of the test instances to examine the effectiveness of the difference components of the BPC algorithm.Lastly,we develop a branch-and-price-and-cut(BPC)algorithm for solving a scheduling problem with two-dimensional constraints.The problem comes from the production and storage of chemotherapy drugs for cancer treatment by intravenous injection.In essence,this problem is actually an uncertain size two-dimensional vector packing problem.We regard the vial for storing anticancer injection as a bin with two dimensional attributes:volume and processing time.The total volume associated to the same bin cannot be great than the volumetric capacity of the bin,but the size of the bin in terms of the dimension of processing time is uncertain.In the dimension of processing time,we only need to ensure that the lateness of the injection does not exceed the given time limit.In order to reduce the number of nodes in the branch-and-bound tree,a rounding inequality(RI)is added to the restricted master problem.To solve the pricing problem,we design a label-setting algorithm with a label dominance rule.In addition,to find integer optimal solution,we also adopt two branching strategies:branching on the number of bins and branching on the forward arc existed in the shortest path problem.Our BPC algorithm is tested on 420 instances that are randomly generated based on the previous literature.We use CPLEX solver to solve the binary integer programming model of the original problem,and the results are compared with those obtained by our BPC algorithm.The results show that our algorithm is much more efficient than CPLEX.In addition,we also conduct computational experiments on a selected set of the test instances to examine the effectiveness of RI in the BPC algorithm.The computational results show that RI can significantly promote the performance of BP.