1 Introduction

With the increasing competition of market economies, many companies are pursuing higher levels of production automation in manufacturing industry. For example, the automated warehouses are employed and play a significant role in the field of manufacturing and processing ^{[1, 2]}. Thus it is meaningful to investigate the automated warehouses scheduling. However, it has not been considered so far that how the LHRL affects the warehouses scheduling efficiency ^[3].

This problem is discussed with one practical application in a certain enterprise. As the storage time of the products of the enterprise is required strictly for a certain time in the process, it can be classified as the production model of the just in time (JIT). This requires a reasonable scheduling for the semi-finished products in the warehouse in order to ensure its quality, which plays a very important role in reducing the cost.

According to the related literature, this type of scheduling can be summarized into two categories ^[4]. One is the stochastic scheduling, which has no model. That is to say, it chooses an object randomly and there is no optimization at all. Therefore, there has little research value on it. The other scheduling is based on model, which produces the optimal solution using the optimization algorithm. Generally, the characteristics of the optimal solution show the shortest path, the least time, the highest utilization of equipments and so on. There has been a great number of literatures on the scheduling of the workshop warehouse up to now. However, some researchers just use intelligent algorithms ^{[5, 6, 7, 8, 9, 10, 11, 12]}, such as the genetic algorithm, the particle swarm algorithm, the niche algorithm, and the neural network, to optimize the path. The path denotes getting out and going into the storage of the products. Some combine the advantage of genetic algorithm and the advantage of simulated annealing to study the lot-sizing scheduling problems, which enhances the utilization of warehouse. Some study the forklift dispatch problem by statistical learning. The statistic information is collected by means of the sensor nodes, and the action of the forklift can be determined ahead of time. Hence it can improve the production efficiency.

However, there are few literatures about the strict control of the storage time of product in the warehouse at present. Sometimes, it may produce many task requests which are about getting out of warehouse at a time in view of the randomness of the production process. Thus, how the semifinished products are scheduled reasonably without affecting the quality makes it a great challenge. Because the traditional static scheduling methods have been unable to meet such requirements, a warehouse scheduling system is modeled based on the weight timeout value of the products which marks the influence degree of the product quality. 2 Illustration of warehouse layout and LHRL

The warehouse system of the enterprise is composed of six parts ^[13]. They are six rows racks, a stacker, two round rails, a pipeline, three input buffers, and three output buffers respectively. Its working principle is that the stacker makes the corresponding action based on the instruction fromscheduling system, which may be described that the stacker goes to the input buffer along the rail and takes the semi-products and put them into the appointed locations, then may pick semi-products required and put theminto the specified output buffer.The warehouse system layout is shown in Fig. 1.

The length l and the height h of warehouse location are shown in Fig. 2, and the LHRL R is expressed as follows,

Equation (1) is used to indicate the shape of the location. Supposing the horizontal velocity and the vertical velocity of the stacker are υx and υy respectively and the location perimeter L is fixed. If there is a semi-product which will be picked at the position P and the P coordinate is (m, n) in Fig. 2. Then the time t which the stacker spend on the task is as follows ^[14],

Equation (2) illustrates that the LHRL change causes the time of stacker spending change for the same tasks. Consequently, the warehouse scheduling efficiency is also influenced by it.

3 Description of warehouse scheduling problem and structure of model

There exists some semi-finished products which have different processes on automation production line, thus they each have different storage time in the warehouse. At the same time, the random of the production is regarded. Therefore, it may cause that those semi-finished products which come out of warehouse at a time compete for the stacker, and then the storage time of the semi-finished products is longer than the normal time to some degree. This problem is even more serious in the case that there are a large number of semi-finished products ^{[15, 16, 17]}.

In order to quantize the problem, the definitions are as follows.

efinition 1 The unit timeout value which affects the degree of the product quality is represented as weight. Depending on the different storage time of product in the warehouse, the weight is defined as follows

Definition 2 According to the locations of the semifinished products and their storage time in the warehouse, a buffer is opened up in the RAM, in which the storage time matrix S_{m × n} and the weight matrix W_{m × n} are generated dynamically corresponding to the semi-finished product in the warehouse, they are defined as

Definition 3 The past time matrix P_{m × n} nindicates the time pass by the semi-finished products since they have been stored in the warehouse, which is defined as

The scheduling model is described as,

The scheduling will be operated in descending order of I_i, the scheduling sequence is showed as,

where il, jl, kl, ..., zl ∈ (1; 2; 3; ..., _{m × n}).

As it always takes the stacker a certain amount of time to carry the semi-finished product out of the warehouse, this scheduling sequence (8) shows a local optimum rather than a global optimum, which is proved as follows.

Supposing

the inequality (9) is also substituted as

Then Δt, I_i and I_j can be rewritten as

The relationship between I_i and I_j is

Therefore, scheduling sequence (8) is not a global optimum.

As proved above, this scheduling model is time-varying. Therefore, the scheduling sequence needs to be updated dynamically all the time to achieve a global optimum. 4 Utilization of sparse matrix in warehouse scheduling

The matrix D_{m × n} is defined as the difference between P_{m × n} and S_{m × n}, in which the element di indicates the timeout corresponding to the location in the warehouse. That’s to say, it can be represented as

Equation (7) can also be expressed as

According to the objective function (15), the semifinished product in the warehouse can be found. If the m × n elements which are gone through in a matrix are calculated and sorted, the number of comparisons is expressed as

The time complexity can be expressed as O((_{m × n}) × log(_{m × n})) from the above formula.

The above method has little effect on the search efficiency when the size of a warehouse is small. Otherwise, it will have a huge influence on the search efficiency. In view of this situation, the rules are defined as follows.

Given a situation that the number of the semi-finished products whose storage time expires is a small part of the whole product in the warehouse in a short period of time, based on which the matrix D_{m × n} is transformed as follows.

If there are some positions in which there are no semifinished products or the storage time of semi-finished products don’t expire or semi-finished products has been placed the scheduling sequence, the elements of the matrix D_{m × n} are assigned to zero corresponding to such positions.

The number of zero elements is much larger than the number of non-zero elements by means of such transformation in the matrix D_{m × n}, so it becomes a sparse matrix, in which only non-zero elements of the matrix are calculated. Then it will improve the calculation and scheduling efficiency greatly. 5 Design of scheduling algorithm based on IoQ strategy

The principle of the scheduling algorithm based on the IoQ parameter is that the IoQs are computed for semi-finished products whose storage time has expired, and the one whose IoQ is the largest scheduled first. With an eye to the different weights and the changing timeout value for such semi-finished products, the IoQs of the rest semi-finished products of the warehouse also keep varying. It is needed to calculate the IoQs to achieve the optimal scheduling on line all the time. The specific scheduling steps are as follows.

Step 1 The mapping two-dimension array a is maintained in RAM according to the size of the warehouse in the actual production. The elements of the table are structure variables which are associated with the semi-finished product. Those variables include the following members:

(i) the warehouse location number of the semi-finished product,

(ii) the storage time of the semi-finished product,

(iii) the weight of the semi-finished product corresponding to the current storage time,

(iv) the start time of the semi-finished product in the warehouse,

(v) the flag which marks whether the semi-finished product has been in the scheduling sequence.

Step 2 The S_{m × n}, W_{m × n} and P_{m × n} are generated from the mapping a at the current time. If the elements of W_{m × n} are all zero, then goes to Step 1.

Step 3 The D_{m × n} is worked out by Eq. (14), meanwhile, the matrix D_{m × n} is transformed to the sparse matrix by the rules of this paper. Then the two-dimension array b is generated whose elements correspond to the non-zero in the sparse matrix D_{m × n}.

Step 4 The IoQs of the semi-finished products are calculated in b according to Eq. (15) and the maximum value among IoQs is placed on the tail of the scheduling sequence. The flag of the semi-finished product, which identify whether it has been in the scheduling sequence, is set as the number one.

Step 5 Under field conditions, the time which the stacker spends to carry the semi-finished product out of the warehouse passes, then go to Step 1. The following semifinished product in the scheduling sequence is obtained. 6 Experimental verification and analysis

The number of the semi-finished product and their timeout values are assumed in the warehouse, and the following agreement is done.

The perimeter of the location is 3 m. υ_x and υ_y are 1 m/s, 0.5 m/s respectively. The products quality or scheduling performance is marked as SoP, which is the sum of the product of the timeout and the weight for every task. The semi-finished products whose timeout value is 10 s is marked as A; in the same way, the semi-finished products whose timeout value is 20 s is marked as B; the semi-finished products whose timeout value is 30 s is marked as C; the semi-finished products whose timeout value is 40 s is marked as D; the semi-finished products whose timeout value is 50 s is marked as E.

The proposed strategy is verified and compared with FCFO ^[18] strategy and random strategy respectively. On the condition whose platform is Windows XP, frequency is 1.49 GHz, memory size is 1.99 GB, development environment is VC++ 6.0.

Table 1 shows that the experiments have six tasks, and each task includes four subtasks. And the XY indicates that the number of timeout category which belongs to Y is X. At the same time, the coordinates of six tasks in the warehouse are shown in Fig. 3, of which X_yz means the product belongs to X, the task and the subtask of which are y and z respectively. Besides, different tasks are labeled with different colors. The numbers at the left side and at the top side of Fig. 3 are represented as layer numbers, column numbers respectively.

Table 2 states that the IoQ strategy is compared with the other two strategies with six tasks respectively under different LHRLs.

From Table 2, it can be seen that the varied LHRL has a great influence on scheduling performance for scheduling strategies. At the same time, the simulation results reveal that the LHRLs corresponding to minimum SoP of different scheduling strategies are different. For example, for the Task 1, the LHRLs corresponding to the minimum SoPs are 1, 0.75 and 0.5 for IoQ, FCFO and RANDOM respectively. Therefore, to get better scheduling performance, it is essential to find a suitable LHRL for different scheduling strategies. Furthermore, it can be observed that the IoQ strategy outperforms the other two scheduling strategies considering all the SoP values, and FCFO is more or less than RANDOM. In other words, the IoQ strategy compared with the others has the smallest impact on the quality of the products.

In order to highlight the advantage of the IoQ relative to the others. The evaluation metric is defined as

where a and b represent the SoP values of different scheduling strategies. The Q(a, b) indicates a is the improvement degree of product quality relative to b. To get clear results of the evaluation, the results can be shown in Fig. 4.

Figure 4 illustrates that the IoQ strategy improve obviously the scheduling performance compared with the other two strategies under different R. Furthermore, the improvement degree varies as the R changes, and the best improvement ratio even reaches 45.4 % and 37.9 % respectively relative to RANDOM and FCFO. Meanwhile, the LHRL values R are different when themetric Q(a, b) gets the peak value for every tasks, and the reason of which is that the timeout weights are various for every subtasks in every tasks, which implies that there is a suitable R for every task and every scheduling strategy. What’s more, it can be deduced that the IoQstrategy is better than the other two no matter what the R is. Therefore, it is also proved that the proposed IoQ strategy is more effective for improving scheduling performance considering the changes of R. In a word, this paper provides a sound theoretical base for the design of the automated warehouse. 7 Conclusions

This paper investigated how the LHRL affects the scheduling performance. Meanwhile, the IoQ mathematical model is built, which is based on the idea that the extent of the unit timeout value which has influence on the product quality. Besides, the scheduling strategy with IoQ is designed. The experiment is performed by scheduling the semi-finished products with different storage time in the warehouse. Comparing with warehouse scheduling strategies, the results show that R has different effect on scheduling performance for different scheduling strategies, and there is a proper R for the best scheduling performance of each scheduling strategy. Additionally, the proposed strategy greatly improves the scheduling performance compared with the other two R changing conditions.

Acknowledgments This work is supported by the National Natural Science Foundation of China (Grant Nos. 61074032 and 61273040), the Project of Science and Technology Commission of Shanghai Municipality (Grant No. 10JC1405000), and the Shanghai Rising-Star Program (Grant No. 12QA1401100).