alexa
Reach Us +44 1704 335730
A GA for the Resource Sharing and Scheduling Problem | OMICS International
ISSN: 2229-8711
Global Journal of Technology and Optimization
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on Medical, Pharma, Engineering, Science, Technology and Business

A GA for the Resource Sharing and Scheduling Problem

Gaby Pinto1*, Uriel Israelí2, Inessa Ainbinder3, Gad Rabinowitz3

1Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Israel

2Department of Technology Management, Holon Institute of Technology, Israel

3Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Israel

*Corresponding Author:
Gaby Pinto
Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Israel
E-mail: [email protected]

Received date: May 2008; Revised date: September 2008; Accepted date: March 2009

Visit for more related articles at Global Journal of Technology and Optimization

Abstract

In this paper we consider the resource-sharing and scheduling problem, with makespan minimization as an objective. Although this problem was optimally solved through a customized branch-and-bound algorithm, its complexity motivated the use of heuristics such as genetic algorithms. A previous genetic algorithm used for solving this problem was significantly faster than the branch-andbound algorithm; however, it suffered from a high rate of infeasible offspring. We propose a new genetic approach, which produces only feasible offspring via a much more compact, genotype representation of the solution. While in the previous genetic algorithm the chromosome consisted of all the solution 0-1 variables (genotype=phenotype), in the new algorithm we define a much smaller chromosome (genotype) that stores sufficient information for efficiently generating a solution for the 0-1 variables (phenotype).

Keywords

genetic algorithm, resource-sharing, scheduling problem, mixed integer linear programming,

Introduction

Within the resource-sharing and scheduling problem (RSSP) as modeled by Rabinowitz et al. [1], a set of precedence constrained operations should be scheduled such that the makespan is minimized. Renewable resources (RRs) required for accomplishing the operations should also be scheduled. An operation may share different RRs simultaneously, each of which may be used for a portion of the operation time. Once started, an operation may not be interrupted (i.e., non-preemptive). Each operation can be performed in one of several modes (Elmaghraby [2]), with each mode representing an alternative assignment of different RRs with different durations. Also, operations may have several sequencing alternatives on each RR according to their precedence constraints. The objective of the scheduling problem is to allocate resources to operations and schedule them to minimize the makespan.

The RSSP arises in various practical scenarios such as production scheduling. However, as shown by Samaddar et al. [3,4], the branch and bound (B&B) algorithm, which is the only optimization procedure available for solving the RSSP, was able to find optimal schedules for only small problems within satisfactory runtimes. Efficient and effective heuristic procedures, therefore, must be developed for larger problems. A heuristic procedure for solving the RSSP has been proposed by Pinto et al. [5]. They proposed a genetic algorithm (GA) which was based on the mixed integer linear programming (MILP) model of Rabinowitz et al. [1], the constraints of which are categorized into two groups, selection-type and time-type constraints. The selection-type constraints guarantee a feasible selection of one mode for each operation and the assignment of tasks for the RRs required by each operation-mode. These constraints contain only 0-1 variables and form the main layer of the model. The time-type constraints involve continuous time variables in addition to the 0-1 variables. Pinto et al. [5] referred to the 0-1 variables and the selection-type constraints as the GA phenotype and proposed a GA based on a phenotype representation (encoding). Once the result of the selection-type constraints and the 0-1 variables is obtained by the GA, production of the time-type constraints and the continuous time variables is easy. This GA suffers from a high rate of infeasible offspring, which is a major issue in the genetic process. Arbitrary crossovers of two feasible solutions often produce infeasible offspring. This can result from one of three possible situations: (1) two operation-modes are assigned as the same resource task number; (2) violation of the precedence constraints of the operation, and (3) gaps of unused resource task numbers. In order to ensure feasibility of the offspring, the GA applies a repair operator to the newly produced offspring. This paper introduces a new GA approach for solving the RSSP. The stepping stone is producing only feasible offspring by using a genotype representation, successfully employed by Hartmann [6] for solving the multi-mode resource-constrained project scheduling problem (MRCPSP). Adopting this approach, we develop a genotype representation that consists of a mode assignment for each operation and a precedence feasible operation list for each resource. The phenotype, i.e., schedule, related to a genotype is generated using the MILP model for the RSSP as presented by Rabinowitz et al. [1].

The remainder of this paper is organized as follows. In Section 2, we briefly present the RSSP. Section 3 describes a new GA for the RSSP. Section 4 presents the basic assumptions, definitions, and theorems regarding the feasibility of the offspring. Finally, Section 5 summarizes the study.

The RSSP

We consider a problem where a predetermined job requires a set of non-preemptive operations image with precedence relationship constraints defined by the immediate predecessor-successor set set S . A set of RRs of the same or different types R = {r} is used to perform these operations. Each operation i can be performed using an alternative mode image A mode m specifies the subset of resources image , as well as the exact timingimage of the use of r during an operation i . An operation may share different resources simultaneously, each of which may be used for a portion of the operation time. Each resource r has Lr sequence locations for its tasks, which are labeledimage defines sequence-dependent delay requirements between operations on a specific resource r . The processing time is assumed to be deterministic and continuous. The problem is to select a single mode for each operation and, accordingly, to allocate and schedule the resources to minimize the makespan time.

A New Genetic Agorithm for the RSSP

This section presents a new GA for solving the RSSP. Introduced by Holland [7], GAs play an important role in solving hard optimization problems. Following the law of nature, the GA recombines existing solutions to obtain new ones. The idea is to produce better solutions by selecting and recombining the best solutions of the current generation. For an introduction to GAs, see Goldberg [8] and Chambers [9]. In this paper, j defines the current individual, and the stopping criteria of our GA was a pre-specified number of generationsG .

Genotype Representation

Our main goal was to develop an individual representation that will produce only feasible offspring. With this idea in mind, we used the genotype representation successfully employed by Hartmann [6] to solve the MRCPSP. We made some changes to Hartmann's genotype representation, however, because of the differences between the MRCPSP and the RSSP.

The individual genotype representation image comprises a precedence feasible operation sequence list image for performing on each resource image and a mode assignmentimage The mode determines which resources will actually perform the operation. If S is the set of the immediate precedence relationship between operations, then for each image there exists a setimage which is the set of all predecessors of operation i . An operation sequence list is precedence feasible if all the predecessors of an operation are sequenced before this operation in the list. That is, if Sip is the set of all predecessors of the p th operation in the operation sequence list, then image A mode assignment m is a mapping that assigns one of its modes image to each operation image . We will use the following alternative notation for the individuals:

image

Since operation i in mode m is not assigned to all the resources, but only to image in contrast to Hartmann [6], for the sequencing step on each r we consider only the operations that were assigned to it by activating the following operator for each i . For each image the corresponding operation i is marked with an asterisk image in the genotype operation sequence list Vr .

For each genotype imagewe produce its phenotype by transforming the genotype into a MILP formulation of the RSSP. The fitness (T ) of individual j is then calculated via a customized critical path method.

Initial Generation

The initial individual for the first generation is produced by repeatedly and randomly selecting the next schedulable operation, choosing its mode, and scheduling the operation as the next task for its resources. This process is repeated until image individuals are produced. Each individual is assigned a reproduction probability based on its fitness function value, which in our case is the schedule makespan time.

Reproduction Probability and Selection

1. Let image denote the transformation function value of individual image

2. Find the total value image of the generationimage

3. Calculate the reproduction probability image for individualimage

Several selection methods were considered, such as the "roulette wheel sampling" method (Goldberg [8]), and all of them follow Darwin's strategy of "natural selection". The selection determines the two parent solutions for "breeding" according to their reproduction probabilities. A parent can be selected more than once or not at all. This selection is repeated image times per generation.

Crossover and Mutation

Once the two parent individuals are selected we use the crossover and mutation operators to produce the two offspring. As the genotype representation of our problem is very unique, we had to develop special crossover and mutation operators. The new operators we present here are based on those developed by Hartmann [6].

Two parent individuals are selected for crossover, imageimage Then two random integers q1 and q2 withimage are generated. From the two parent individuals, two offspring are produced, imageimage The crossover algorithm contains two stages, the assignment stage and the sequencing stage. The stages for producing offspring jO1 are described as follows (offspring jO2 is produced in the same way).

Assignment Stage – The mode assignments of the offspring are produced as follows:

image

Sequencing Stage – The operation sequence list image for each resource image of the offspring is defined and the operations assigned to resource r are marked by an asterisk as follows:

Set image and the operation sequence list of positions image inimage is taken fromimage by the following procedure:

For image do:image

For image do: Ifimage thenimage

For image do: Ifimage then markimage by an asterisk

End For

A mutation approach is applied for some of the newly produced offspring. We used two mutation operators, one for the mode assignment m and another for the operation sequence list image The offspring to be mutated are chosen by a small mutation probability image andimage for the mode assignment and for the operation sequence list accordingly. The mutation operator for the mode assignment m changes the modes assigned for each operation randomly. For each image and a mode m(i), a different or the same mode assignment m is selected. The mutation operator for the operation sequence listimage changes the sequence list of operations on resource r (randomly selected). For all the resource tasks image operationimage are swapped only if a precedence feasible operation list is received.

Fesibility of the Offspring

In this chapter, we provide the basic assumptions, definitions and theorems regarding the feasibility of the offspring. Due to the limits on the size of the paper, the proofs are not provided. Assumption 1 – For an assignment problem with image andimage all the combinations of modes are legal.

This means that no special interrelation constraints among the operation-modes image s are considered in this paper.

Assumption 2 – When sequencing a set image of operations with image on a single resourceimage all the permutations are legal.

Definition – A feasible genotype is aimage whereimage is a Boolean function on j and the pairimage represents the genotype and its feasibility status.

The function image receives true when offspring j is feasible, namely, it has a legal precedence operation sequence list image for each resource image and a legal mode assignmentimage We note that although in most scenarios a feasible genotype will lead to a feasible phenotype, this is not always guaranteed, as will be elaborated later.

Theorem 1 – For an RSSP withimage andimage from two feasible parent genotypesimage andimage the GA produces two feasible offspring genotypes image andimage

Notice that when the order between two operations is not restricted by S , there may be task sequences of different r s that contradict each other by dictating conflicting orders for performing these two operations. image be the set of shared resources of operations-modes image andimage

Definition – A cross schedule is an opposite sequence order between two operations-modes on two different resources as follows.

For image the sequence on resource imageand the sequence on resource rk is image

Theorem 2 – For an RSSP, the genotype-phenotype transformation algorithm produces a single feasible phenotype (of the earliest time for each operation) from a feasible genotype that does not have any cross schedule.

When a cross schedule does exist in a genotype, the existence of a feasible phenotype depends on the specific problem parameters.

Summary

In this paper we proposed a solution to the RSSP via a GA that produces only feasible genotype offspring. The GA preserves offspring feasibility by employing a proper problem representation and using suitable genetic operators. The representation of the problem plays a major role in the success of the GA. In addition, the specific crossover and mutation operators that we used guarantee the feasibility of the offspring without loosing the evolutionary nature of the GA. Development of a generic tool for applying our GA to solve RSSPs and conducting empirical experiments is left for future research.

References

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Article Usage

  • Total views: 11827
  • [From(publication date):
    June-2010 - Dec 11, 2019]
  • Breakdown by view type
  • HTML page views : 8043
  • PDF downloads : 3784
Top