Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

New Meanings to Old Rituals : The Emergence of Mourning Rituals in Shiʿite Islam

This paper will discuss the emergence of Shiʿite mourning rituals around the grave of Husayn b. ʿAli. After the killing of Husayn at Karbala’ in 61/680, a number of men in Kufa feel deep regret for their neglect to come to the help of the grand­son of the Prophet. They gather and discuss how they can best make penitence for this crime. Eventually, they decide to take to arms and go against the Umayyad army – to kill those that killed Husayn, or be killed them­selves in the attempt to find revenge for him. Thus, they are called the Penitents (Ar. Tawwābūn). On their way to the battlefield they stop at Husayn’s tomb at Karbala’, dedicat­ing themselves to remorseful prayer, crying and wailing over the fate of Husayn and their own sin. When the Penitents perform certain ritual acts, such as weeping and wailing over the death of Husayn, visiting his grave, asking for God’s mercy upon him on the Day of Judgment, demand blood revenge for him etc., they enter into already existing rituals in the pre-Islamic Arab and early Muslim context. That is, they enter into rituals that were traditionally performed at the death of a person. What is new is that the rituals that the Penitents perform have partially received a new content. As described, the rituals are performed out of loyalty towards Husayn and the family of the Prophet. The lack of loyalty in connection with the death of Husayn is conceived of as a sin that has to be atoned. Blood revenge thus be­comes not only a pure action of revenge to restore honor, but equally an expression for true religious conversion and penitence. Humphrey and Laidlaw argue that ritual actions in themselves are not bearers of meaning, but that they are filled with mean­ing by the performer. Accord­ing to them, ritual actions are apprehensible, i.e. they can be, and should be filled with meaning, and the people who perform them try to do so within the context where the ritual is performed. The story of the Penitents is a clear example of mourning rituals as actions that survive from earlier times, but that are now filled with new meaning when they are performed in a new and developing move­ment with a different ideology. In later Shiʿism, these rituals are elaborated and become a main tenet of this form of Islam.

From the road network database to a graph for localization purposes

The problems of finding best facility locations require complete and accurate road network with the corresponding population data in a specific area. However the data obtained in road network databases usually do not fit in this usage. In this paper we propose our procedure of converting the road network database to a road graph which could be used in localization problems. The road network data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The population points are also processed in ordered to match with that graph. The reduction of the graph is done maintaining most of the accuracy for distance measures in the network.