A new class of assignment problem which roots in the optimization management of slabs in steel industry is considered in this article. Compared with the generalized assignment problem, flow constraints should be considered in this problem besides the capacity constraints when assigning items to knapsacks. This problem could be reduced to the generalized assignment problem, and so is NP-hard. A heuristic with oscillation strategy and long-term memory list is proposed to solve it. The oscillation strategy makes it possible that the local search oscillates between the feasible and infeasible solution spaces to find better feasible solutions. A long-term memory list is embedded to encourage the diverse moves of items, which improves the diversity of the algorithm. In order to testify the efficiency of the heuristic, 23 instances have been randomly generated for the computational experiments. The results show that for small-size instances, the maximum deviation of the heuristic from the optimal solution is 0.55% and for larger-size instances, the heuristic could find good solutions in a very short time.
A new class of assignment problem is considered in this article, which is an extended version of general assignment problem (GAP). This problem can be described as follows. The item j in set J (J={1, 2,..., n}) will be assigned to one of the knapsacks in set I={1, 2,..., m} to maximize the assigning profit, while the knapsack capacity constraints should be satisfied, as well as the flow constraint. The flow constraint indicates that the knapsacks belong to different types, and
the total weight of items in each type should be no less than a predetermined value number.
This problem arises from the steel production. In most iron and steel companies, production is stimulated by customer orders, and the planning and scheduling of semiproducts during the production is arranged according to the actual requirements of various orders. With the development of motor industry, household electrical appliance industry, and property industry, it is very usual that the customers order small amount but various steel products. However, the
orders conflict the mass feature of steel production. For example, in steel-making stage, steel-making furnaces produce molten steel (it will be made to slabs in casting stage) in either
300 ton or 250 ton batches, which are not exactly the ordered amounts most of times. So the production of small amount and various products usually results in unsatisfied matching relationships between the slabs and orders. It is also the reason the produced slabs often exceed the actual required amount. Consequently, the customer satisfaction
level decreases and production cost rises. An effective way of avoiding these deficiencies is to reallocate the slabs for maximizing the matching profit by optimization method after releasing the original matching relationships. The new matching relationships should satisfy the
following constraints: 1) the total slab weight allocated to each order should not exceed the order’s requirement and 2) the slab weight allocated to the orders for each material flow
should be not less than its requirement in order to ensure the balance of production, while the orders belong to different material flows (a material flow corresponds to one main downstream production operation for the products required by orders). If slabs are seen as items, orders as knapsacks and the material flow as knapsack’s flow, the above problem is actually assigning items to knapsacks to maximize the assigning profit with the two constraints on knapsack capacity and knapsack flow. So the problem is an extended version of the GAP. However, compared with the GAP problem, the new problem is more complex for the new constraint on flow. The GAP is an NP-hard problem[1], so it is claimed that the assigning problem with flow constraint is also an NP-hard problem. For such kind of problem, optimization
method is hard to solve within a reasonable short time, and the intelligent optimization method is often adopted instead. The discussed problem has two kinds of constraints, and the feasible space is relatively narrow. Oscillation strategy[2−3] is an effective search strategy for the problem with narrow feasible solution space. It comes from tabu
A new kind of assignment problem is considered in this article, in which a new constraint on flow should be satisfied besides the one on knapsack capacity when assigning the items to knapsacks. A heuristic with oscillation strategy is constructed to solve the problem, in which the search runs alternatively between feasible and infeasible solution spaces to obtain better solutions. Long-term memory list isintroduced to encourage the various assignments of items,
which is helpful to enhance the diverse search ability of the algorithm. The computational results on 23 instances show that the maximum deviation of the results obtained by theheuristic and the optimal solution for small-scale instances is 0.55%, and the heuristic can obtain satisfied near-optimal solutions in a short time for the relatively large-scale instances.The experimental results indicate the heuristic with oscillation strategy and long-term memory is effective to the problem with narrow or discontinuous feasible solution space.
