A Modified Ant Colony Algorithm to the P| Prec| Cmax Scheduling Problem: A Comparative Study

A Modified Ant Colony Algorithm to the P| Prec| Cmax Scheduling Problem: A Comparative Study

Mohamed Messaoudi-Ouchene (LAMDA-RO Laboratory, Mathematics Department, Faculty of Science, University Saad Dahlab of Blida, Blida, Algeria) and Ali Derbala (LAMDA-RO Laboratory, Mathematics Department, Faculty of Science, University Saad Dahlab of Blida, Blida, Algeria)
Copyright: © 2013 |Pages: 10
DOI: 10.4018/ijamc.2013070105


This paper investigates a comparative study which addresses the P/prec/Cmax scheduling problem, a notable NP-hard benchmark. MLP_SACS, a modified ant colony algorithm, is used to solve it. Its application provides us a better job allocation to machines. In front of each machine, the jobs are performed with three priority rules, the longest path (LP), a modified longest path (MLP) and a maximum between two values (MAX). With these three rules and with both static and dynamic information heuristics called “visibility”, six versions of this ant colony algorithm are obtained, studied and compared. The comparative study analyzes the following four meta-heuristics, simulated annealing, taboo search, genetic algorithm and MLP_SACS (a modified ant colony system), is performed. The solutions obtained by the MLP_SACS algorithm are shown to be the best.
Article Preview

1. Introduction

Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to jobs over given time periods and its goal is to optimize one or more objectives. The first scheduling algorithms were formulated in the mid fifties. Since then, there has been a growing interest in scheduling. During the seventies, computer scientists discovered scheduling as a tool for improving the performance of computer systems. Scheduling problems have been investigated and classified with respect to their computational complexity. During the last few years, new and interesting scheduling problems have been formulated.

The resources and jobs in an organization can take many different forms. The resources may be machines in a workshop, runways at an airport, processing units in a computing environment, and so on. The jobs may be operations in a production process, take-offs and landings at an airport, stages in a construction project, executions of computer programs, and so on. Most parts of the Bruckers’s book (Brucker, 2007) are devoted to the discussion of polynomial algorithms. In addition, enumerative procedures based on branch & bound concepts and dynamic programming, as well as local search algorithms are presented. Methods of combinatorial optimization that are relevant for the solution procedures and computational complexity theory are stated. Each job may have a certain priority level, an earliest possible starting time and a due date. One objective may be the minimization of the completion time of the last job and another may be the minimization of the number of jobs completed after their respective due dates (Pinedo, 2008). The scheduling problem, on identical parallel machines, to precedence constraints denoted P|prec|Cmax is often stated to be a NP-hard problem (Brucker & Knust, 1998). Such scheduling is done in two phases: the allocation of jobs to machines and the sequencing of jobs on each machine. An exact solution is only effective if the number of jobs is reduced. Our goal is to minimize the scheduling length or the completion time of the last job. This criterion is important because the scheduler ensures load balancing between machines. We consider only the non-preemptive scheduling. Once a job begins execution, it can not be interrupted. The time required to execute a given job is known in advance and does not depend on the machine used. Precedence relations may exist between jobs and are given by a graph. In scheduling on parallel machines, the most commonly used algorithms are lists of types. They determine, to a range of jobs given by a list, the corresponding scheduling. They consider the jobs one by one and make the decision to schedule based on a partial ordering of already sequenced jobs. For many difficult problems in a wide variety of areas, meta-heuristics have received considerable interest and have proven effective in various fields such as industrial, economic, logistical, engineering, trading, science, etc.. Phelipeau-Gelineau (Gelineau, 1996) developed a taboo search algorithm to solve the P|prec|Cmax problem. Alba (2005) brings both the parallelism and metaheuristic fields with a main focus on optimization. It contains a methodological part dealing with a specified technique, discusses how parallel models can be derived for this technique to become more efficient. Some experimental analysis is included. Complex optimization problems abound in the real world. In the face of these challenges, established methods often fall short of providing good solutions. However, ‘exact’ and ‘heuristic’ techniques are dramatically enhancing our ability to solve significant practical problems in the world of optimization.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing