خوارزم الغربلة SOA

The recently developed Shaking Optimization Algorithm has been used here in this research to solve the problem. This SOA algorithm follows the common methodology of the Evolutionary Computations. In EC, simulated evolution is implemented by the application of various operators such as mutation and recombination in a random manner. The proposed algorithm is a structured search algorithm that applies a number of heuristics during this search process. It starts with reordering the operations (of all jobs) according to some criteria (weight). Due to this rearrangement, gaps may exist. To close these gaps, another heuristic can be applied. The process of reordering and gap closing is to be repeated many times until some stopping criteria is met. It is a hierarchy of four consecutive stages: local search, collision, fine tuning and global optimization as shown by the Pseudo-code in Figure 1.

Stage 1, Local Search

The proposed approach assumes that the solution at any time is a set of items of different sizes that are ordered in one raw tangent to each other. The objective is to find the order that gives the minimum length of that raw. This can be done through shaking these items in all directions (x & -x, y & -y, z & -z) searching for the shortest possible raw.

The coordinate system is not a real x-y-z system but it is a system of priority rules that manage the searching process of the solutions. So, one can assume that shaking along the x-axis, as an example, force the items to reorder themselves in an ascending order according to their size as a result of their inertia, and so on.

Stage 2, Collision

It is assumed that the local search process will result in some gaps in-between items leading to the Collision stage. In the Collision stage, if a gap exists between item (A) and item (B) then, due to the shaking process item (A) will hit (B) giving it a push in the same direction of the shake forcing it to jump to another location. If this new location is not
better than the original one, then item (B) will return back resulting in a push to (A), which in return will jump to another location in the direction of this push. The definition of “gap” may be the delay time of a job or be the
idle time of a machine.

Stage 3, Fine Tuning

At the end of each shake or number of consequent shakes, the movement of the items will start to slowdown resulting in the Fine tuning stage. In this stage, some items, where gaps exist around them, start to swap or rotate around its center resulting in better penetration according to the nature of the problem under consideration. The items allowed to swap or rotate are those items come just after a gap or followed by a gap, i.e., those items at the beginning or at the end of a block. The rule that most describes this swapping action is the one of Nowicki and Smutnicicki (1996) and has been described by M. Emin and Terence C.

Stage 4, Global Optimization

To recover from or avoid penetration in a local optimum the Global optimization stage is to be activated. After a certain number of iterations “Shakes”, or at any other criteria, a new initial solution is to be developed based on the best solution so far.


Procedures of the shaking algorithm

The proposed algorithm utilizes a number of heuristic rules through the four consecutive stages as follows:

Stage 1, Local Search

The problem is to be represented using a suitable coding system, and then a random initial solution is to be developed. Following this, the coordinate system that will be used in the evolution of this random solution is to be identified. This coordinate system is to be represented by a selected number of priority rules. The shaking force is to be defined after, where this force defines the number of elements (objects) that are going to change their positions at each shake. Each of the selected rules is to be applied individually, then if improvement exists, the resulting solution will be kept, and the remaining rules should be applied on this new solution.

أعلان هام

إعلان هام

أرقام الاتصال

غرفة رقم أد030 / 3 بمبني مجمع الكليات

تحويلة رقم 2544


نتائج الطلاب


إحصائية الموقع

عدد الصفحات: 37

البحوث والمحاضرات: 13

الزيارات: 7014