Article Preview
Top1. 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.