Search

In this work, we focus on the scheduling of multi-crane operations in an iron and steel enterprise for a two-stage batch annealing process. The first stage is the heating process, and the second stage is the cooling process. To start the heating (cooling) stage, a special machine called a furnace (cooler) must be loaded. The real constraints of no-delay machine unloading are defined as follows: once the heating (cooling) is completed, the furnace (cooler) must be unloaded by crane immediately. The goal is to schedule limited machines (furnaces and coolers) operated by multiple cranes to minimize the completion time of the last annealed coil (makespan). We formulate a mixed-integer linear programming model to address this problem. Certain feasible properties are identified to avoid crane conflicts and ensure that the machine unloading no-delay constraints are met. Based on these necessary conditions, we then present a heuristic algorithm with running time in connection with the number of cranes, coils and machines. A lower bound to the problem is also developed. Through theoretical analysis, we show the worst-case bound of our heuristic algorithm. The average performances of the solution approaches are computationally evaluated. The computational results show that the proposed heuristic algorithm is capable of generating good quality solutions.

This paper considers a multi-crane scheduling problem commonly encountered in real warehouse operations in steel enterprises. A given set of coils are to be retrieved to their designated places. If a required coil is in upper level or in lower level without being blocked, it can be picked up directly to its designated place; else, the blocking coils need to be picked up to another position first. Our problem aims to determine which positions for blocking coils to be shuffled to, and a joint transportation sequence of required coils to the designated places and blocking coils to be shuffled as soon as possible by multi-crane carrying these coils simultaneously. For describe the studied problem clearly, we first formulate it as a mixed integer linear programming (MILP) model. Then some feasible and optimal properties for assigning cranes to avoid collisions in possible positions are identified. Since a special case of our problem is demonstrated strongly NP-hard, we further propose a heuristic algorithm. A lower bound to the problem is developed and the performance of the heuristic algorithm is analyzed from the worst case point of view. Finally, computational experiments are used to evaluate the average performance of our proposed methods and the results show that the proposed heuristic algorithm is capable of generating good quality solutions.

In this paper we considered a scheduling problem including both production and job delivery, with machine availability and job rejection considerations. The objective is to minimize the arrival time of the last delivery batch of accepted jobs to the distribution center plus the total penalties of rejected jobs. Based on this NP-hard problem, we propose a heuristic with a worst-case error bound of 6, and the algorithm running time is O(nlogn).

We investigate a single machine scheduling problem with a fixed unavailability interval on machine and rejection job. The objective is to minimize the sum of the flow-time of the accepted jobs and penalties of rejected jobs. For the demonstrated NP-hard problem, we first propose a dynamic programming algorithm for solving small scale problem optimally. Further we propose an approximation algorithm to obtain a better worst case bound.

This paper studies a single crane scheduling problem arising in the cold-rolling material warehouse in an iron and steel enterprise. A set of coils stored in two levels are needed to be picked up and transported to designated positions. If a required coil is at the upper level, it can be picked up right away and transported to its designated position (transportation operation). A required coil at the lower level cannot be picked up until all its blocking coils at the upper level are moved to other positions (shuffling operation). One overhead crane is used to perform all the transportation and shuffling operations. Our problem is to schedule the crane operations so as to all required coils retrieve to their designated positions in the shortest possible time (makespan). Since the problem is shown to be NP-hard, a genetic algorithm (GA) is proposed. We identify some analytical properties which enable us to develop an effective heuristic algorithm as initial solutions of the GA. We further analyze its performance from the worst-case point of view. To evaluate the average performances, a numerical test compared with some existing methods is carried out and its results show the good quality of the proposed algorithm.

This paper focuses on a single crane scheduling problem in order to pick all demanded coils for downstream stage production or for customer which is motivated by cooled-rolling material warehouse in the iron and steel enterprise. If a demanded coil is in the upper level, it can be picked up directly to designated place (transportation operation). If a demanded coil in the lower level is blocked by one or two un-demanded coils, the coil can not be transported until all the blocking coils are picked up to another position (shuffling operation). Both the transportation and the shuffling operations are performed by a mounted traveling crane. Our problem combines transportation and shuffling simultaneously for crane to pick up all demanded coils as early as possible to designated place, that is, the optimality criterion considered is the minimum makespan. We show its complexity by reduction from a demonstrated strongly NP-hard problem. Furthermore we introduce a dynamic programming (DP) for solving the problem optimally.

For designing wireless sensor networks, the coverage of the sensing area, sink location and data routing are three major issues. This paper considers three technique problems within a unified framework and develops a mixed-integer linear programming formulation. Further, a hybrid meta-heuristics is proposed to solve the solution. The outer loop of this procedure uses filer-and-fan to identify the best sensor locations, while in the inner loop sink locations and data routing are determined in the best way for the sensor locations fixed by the outer loop. Computational examples are presented and the results indicate that the proposed meta-heuristics is both effective and efficient.

This paper investigates a master-plate design problem encountered in the heavy plate mill of the steel industry. The aim of the problem is to pack customer rectangle order-plates into master-plates under consideration of satisfying guillotine cuts, no rotation and no overlap constraints. Unlike the classical two-dimensional bin packing problem, the master-plate design problem we study is a more general case which is not only to determine the size of each order-plate within a specified range but also to decide the size of each created master-plate. The effective design for this problem can help to reduce the trim loss of the master plate, reduce the production cost and improve the material design quality. We formulate this problem as a mixed-integer program, and present an improved lower bound which is based on the split and recompose methods for verifying the effectiveness of a proposed algorithm. Computational experiments show that the improved lower bound is comparable with the one existed in the literature.

This paper addresses a multi-crane scheduling problem that incorporates scheduling shared two-category limited number of machines motivated by batch annealing process (BAP) in the iron and steel factory. In this process, each coil subjects to a long heat-treatment cycle by varying the temperature within furnace (machine) and cooler (machine) which are operated by crane orderly. The objective is to minimize the annealing completion time of the last coil (make span). We propose a two-phase heuristic algorithm which consists of assignment and scheduling. Based on a dynamic programming, the assignment phase is to assign each crane to its exclusive sub-block, followed by machine assignment to each sub-block. Scheduling phase adopts an earliest requirement operated stage first strategy. Finally, the effectiveness of the proposed algorithm is theoretically analyzed from an absolute performance point of view.

This paper investigates the problem of multi-crane scheduling in batch annealing process in steel enterprises so that the completion time of the last annealed coil (makespan) is minimized. In the annealing process, each coil consists of two-stage processing: heating and cooling. To start heating (cooling) stage, a special machine named furnace (cooler) must be loaded on. Once the heating (cooling) is completed, the furnace (cooler) must be unloaded immediately without any delay by crane (machine unloading no-delay constraints). The aim of our studied problem is to schedule limited machines (furnaces and coolers) operated by multiple crane to process jobs with avoiding collisions between two adjacent cranes and guaranteeing machine unloading no-delay constraints. For this demonstrated strongly NP-hard problem, we present a heuristic algorithm combined earliest job requirement and closest crane first with running time in connection with the number of cranes, jobs and machines. Then we propose some properties for deriving a lower bound to verify the performance of the proposed heuristics. Through the theoretically analysis, we show the worst case bound of our heuristic algorithm.

This paper investigates scheduling parallel machines with a single sever as well as additional constraints on setups and removals. It generalizes classical parallel machine scheduling problem with a single server which needs to perform setup operation of each job only. This model is motivated by a key course of batch annealing process in the steel industry: heating or cooling. The objective is to minimize makespan. For this problem, we first give some complexity results by reduction. Some optimal properties are derived. Based on the properties, a LPT heuristics is proposed which generates a tight worst-case bound 3/2-1/2m.

The paper researches a scheduling method based on variable neighborhood search (VNS) for a dynamic crane scheduling problem abstracted from steel making process in the iron and steel enterprise with random torpedo car arrivals and empty ladle breakdowns. Our objective is to minimize both makespan and total tardiness. At any rescheduling point, weights derived from artificial neural network (ANN), proper parameters for VNS are calculated that significantly enhances the performance of the scheduling method. Computational experiments indicate that the proposed method is better than those of common heuristic rules.

This paper investigates the mother plate design (MPD) problem encountered in the heavy plate mill of the steel enterprise. The aim of the problem is to pack rectangular order plates (that need to be produced) into mother plates that satisfy guillotine and materials constraints. We develop a hybrid algorithm based on scatter search. Two adaptations of Finite Best Strip and Finite First Fit are developed to construct the placement of the order plates, and a simple tabu search algorithm is developed to improve the packing quality of the current packing solution. Computational experiments show that the hybrid algorithm can provide very satisfactory results in a reasonable time.

This paper investigates the steel grade assignment problem daily encountered in the iron and steel industry, which involves the determination of which candidate steel grades to be employed in order to satisfy as many collective customer orders as possible such that the number of employing new steel grades and the desirable costs of satisfying the customer orders from the employed steel grade are minimized. The problem is formulated as a mixed integer programming model in which customer orders are optional. In addition, it displays the characteristic of the uncapacitated facility location problem. A midpoint-based method is proposed to obtain the desirable costs for the ability of steel grades to satisfy the requirements of orders. We develop a Lagrangian relaxation based (LR-based) heuristic approach with hybrid improvements including local search for the problem. The algorithm has been tested on instances collected from practical production data. Computational results demonstrate the effectiveness of the approach even for realistic problems with larger instances.