Theoretical Research On Crane Logistics Scheduling Problems In Operations Management Of Steel Industry

The iron and steel industry is one of the mainstay industries of the national economy. In recent years, along with the rapid development of building industry, motor industry, shipbuilding and home appliance industry, there will be higher requirements for the quantity and quality of the steel. The production process of iron and steel industry is very complicated, the relation among the stages of production is compact, and the logistic net is cross. Since jobs producted is continuous and delivered is high temperature characteristic, job delivering time between continuous working procedures is rigorous. Job is transported among the production processes heavily by a carrying tool--crane. Effective crane schedule of steel production and logistics is helpful to decrease jointed time among processes, shorten waiting time, improve utilization ratio of crane, and reduce waste of resource and energy. Therefore, it becomes a challenging and interesting research topic to analyze crane logisitics scheduling problem in operations management of steel industry from the theoretic perspective, post the inherent rule of the operations and the schedules among the production and logistics, and develop effective approximation algorithms for the complex and impalpable problems.The problems in this theoretical research are abstracted from batch annealing process and steel warehouse. We study a single crane scheduling with tool carried in batch annealing process, multiple crane scheduling in batch annealing process with tool no-delay constraints, multiple crane scheduling in batch annealing process with job and tool carried jointly, scheduling parallel machines with a single server, jointly transportation in crane scheduling, a single crane scheduling problem with integrated shuffling and transportation operation in steel warehouse and multiple crane scheduling with integrated shuffling and transportation operation in steel warehouse. From algorithm complexity, easy-solving and hard-solving point of view, we give a theoretical research for these problems. Based on the complexity analysis, for the easy-solving problem, we present the optimal polynomial time algorithm, for the general case of the hard-solving problem, we construct effective heuristic approximation algorithm, and also we analyze and evaluate the effectiveness of the algorithm by using worst case analysis and asymptotic case analysis, for the special cases, we analyze the optimal solution property and develop the effective algorithm. The content is summarized as follows.1) A single crane scheduling with tool carried in batch annealing process.In batch annealing process, furnace and cooler which are considered as tools in heat treatment need to be loaded and unloaded according to different stages. All the loading operations and unloading operations are performed by crane. For a single crane, how to decide operation sequence and schedule crane for minimizing a given objective, it is a practical optimal problem. For the problem, a mixed integer programming (MIP) model is formulated. We show that the problem is NP-hard in the strong sense. Some optimal properties on the problem are derived. A heuristic algorithm is constructed and analyzed from an absolute performance point of view. We also consider special cases where some optimal properties and polynomial solvable optimal algorithm are developed.2) Multiple crane scheduling in batch annealing process with tool no-delay constraints.We extent a single crane scheduling with tool carried in batch annealing process to multiple crane scheduling case with no-delay constraints for tool unloading to decide crane allocation, crane route and timetable. For the problem with objective to minimize makespan, we show that the problem is strongly NP-hard. Some feasible properties are identified to avoid crane collisions and guarantee tool unloading no-delay constraints. Based on these properties, we present a heuristic algorithm and show the worst case bound of the algorithm. A special case is demonstrated to be solved optimally in polynomial time.3) Multiple crane scheduling in batch annealing process with job and tool carried jointly.In the problem, job (coil) and tool (furnace, cooler) are considered to be loaded and unloaded jointly. All these operations are performed by multipe crane. The problem needs to decide crane allocation, crane route and timetable. For the problem, we formulate a MIP model, develope some analytical properties, and propose an aggregate approach to reduce problem difficulty but keep the essential features of the practical problem. We propose a two-phase heuristic algorithm which consists of assignment and scheduling. From an absolute performance point of view, we measure the quality of the proposed heuristics. We also propose a tool assignment based heuristics and analyze it from an absolute worst-case performance an asymptotic worst-case performance, respectively.4) Scheduling parallel machines with a single server.Loading and unloading operations for jobs in cooled rolling parellel production line are performed by crane (or crarrier), when there is only one crane, the problem can be reduced to scheduling parellel machine with a single server. Different from classical parallel machine scheduling problem with a single server, a server in our model performs job with not only setup time but also removal time. We give some complexity results by reduction. Some optimal properties are derived for more general problem with an arbitrary number of machines. Based on the properties, we construct polynomially solvable heuristic algorithms for the problem concerning two situations:with and without dedicated machine. For prior situation, a tight worst-case bound of the heuristics is shown at most twice. For latter situation, a LPT heuristics generates a tight worst-case bound3/2-1/2m. Moreover, a polynomially solvable case is also given.5) A hub reentrant job shop scheduling modeling scheme based scheduling crane problem.As one job is loaded or unloaded according to different operating requirement in batch annealing process, it is operated several times by one crane. If a crane is considered as a hub reentrant machine, and furnace and cooler are considered as two classes of machines, the problem can be reduced to a hub reentrant job shop scheduling modeling scheme based scheduling crane problem. We mainly consider two problems. The first problem is the case that there is only one machine in each class. The second problem is the case that there are some machines in each class. For the first problem, we show that the problem is NP-hard in the strong sense and derive some properties that identify a specific optimal schedule. Furthermore, a heuristic algorithm is proposed with the makespan at most6/5times (bound) that of an optimal schedule and this bound is demonstrated tight. For the second problem, two well solvable cases are proposed respectively.6) Scheduling crane jointly transportation problem based on a two-stage hybrid flowshop problem scheme.Before batch annealing process, coils are transported by trolly to workshop, and then carried by crane. After batch annealing process, coils are carried by crane to trolly, and then transported by trolly to workshop. In such process, if crane and trolly are considered as machine respectively, we abstract a two-stage hybrid flowshop problem. We present a heuristic algorithm and analyze the worst-case performance bound3-2/m1,(m1is the machine number of the first stage).7) A single crane scheduling problem with integrated shuffling and transportation operation in steel warehouse.The problem considers scheduling integrated shuffling and transportation operation of crane in steel warehouse to decide the transportation sequence of demanded coils, the target positions which blocking coils to be shuffled move to, crane route, and timetable. For the problem, we propose a MIP model and show that its complexity is strongly NP-hard. Some analytical properties are provided. Based on these properties, we propose a polynomial-time optimal algorithm for solving a special case, and furthermore we introduce a dynamic programming for solving small scale of the general case, respectively. Alternatively, for the large scale of the general case, a heuristics is developed and then analyzed from worst-case performance point of view.8) Multipe crane scheduling problem with integrated shuffling and transportation operation in steel warehouse.We extent a single crane scheduling problem with integrated shuffling and transportation operation in steel warehouse to multiple crane scheduling case by guaranteeing no-collisons among cranes for deciding the transportation sequence of demanded coils and the position of blocking coils to be shuffled. For the problem, we formulate it as a MIP model and identify some feasible properties for assigning cranes to avoid collisions. We show that the problem is strongly NP-hard. A lower bound to the problem is developed. A heuristic algorithm is proposed and the performance of the algorithm is further analyzed from the worst case point of view. We further give a polynomially optimal heuristics for a special case.