Reach Us
+44 1704 335730

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

^{2}Department of Technology Management, Holon Institute of Technology, Israel

^{3}Department 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

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).

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

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.

We consider a problem where a predetermined job requires
a set of non-preemptive operations 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 A mode m specifies the subset of
resources , as well as the exact timing 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
L_{r} sequence locations for its tasks, which are labeled 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.

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 comprises a precedence feasible
operation sequence list for performing on
each resource and a mode assignment 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 there exists a set 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
S_{ip} is the set of all predecessors
of the p th operation in the operation sequence list, then A mode assignment m
is a mapping that assigns one of its modes to each
operation . We will use the following alternative notation
for the individuals:

Since operation i in mode m is not assigned to all the
resources, but only to 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 the corresponding
operation i is marked with an asterisk in the genotype
operation sequence list
V_{r} .

For each genotype we 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 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 denote the transformation function value of individual

2. Find the total value of the generation

3. Calculate the reproduction probability for individual

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 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, Then two random integers
q_{1} and
q_{2} with are generated. From the two
parent individuals, two offspring are produced, The crossover algorithm
contains two stages, the assignment stage and the
sequencing stage. The stages for producing offspring j^{O1} are described as follows (offspring j^{O2} is produced in the
same way).

__Assignment Stage__ – The mode assignments of the offspring
are produced as follows:

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

Set and the operation sequence list of positions in is taken from by the following procedure:

For do:

For do: If then

For do: If then mark 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 The offspring to be mutated are
chosen by a small mutation probability and 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 and a mode *m(i)*,
a different or the same mode assignment m is selected. The mutation operator for the operation sequence list changes the sequence list of operations on resource r
(randomly selected). For all the resource tasks operation 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 and all the combinations of modes are legal.

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

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

**Definition **– A feasible genotype is a where is a Boolean function on j and the pair represents the genotype and its feasibility status.

The function receives true when offspring j is feasible, namely, it has a legal precedence operation sequence list for each resource and a legal mode assignment 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 with and from two feasible parent genotypes and the GA produces two
feasible offspring genotypes and

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. be the set of shared resources of operations-modes and

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

For the
sequence on resource and the sequence on resource r_{k} is

**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.

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.

- G. Rabinowitz, A. Mehrez and S. Samaddar, Scheduling model for multi-robot assembly cells, The International Journal of Flexible Manufacturing Systems 3, pp. 149-180, 1991.
- S.E. Elmaghraby, Activity network: project planning and control by network models. John Wiley, New York, 1977.
- S. Samaddar, G. Rabinowitz and A. Mehrez, Resource sharing and scheduling for cyclic production in a computer-integrated manufacturing cell, Computers& Industrial Engineering 36 (3), pp. 525-547, 1999.
- S. Samaddar, G. Rabinowitz and G.P. Zhang, An experimental analysis of solution performance in a resource sharing and scheduling problem, European Journal of Operational Research 165, pp. 139-156, 2005.
- G. Pinto, I. Ainbinder and G. Rabinowitz, A Genetic Algorithm-Based Approach for Solving the Resource Sharing and Scheduling Problem, Computers & Industrial Engineering Journal, 57 (3), pp. 1131-1143, 2009.
- S. Hartmann, Project scheduling with multiple modes: a genetic algorithm, Annals of Operations Research 102, pp. 111-135, 2001.
- H.J. Holland, Adaptation in natural and artificial systems, Ann Arbor, Michigan: The University of Michigan Press, 1975.
- D.E. Goldberg, Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Massachussetts, 1989.
- L. Chambers, Practical Handbook of Genetic Algorithms 1, Applications, CRC Press, Boca Raton, Florida, 1995.
- C. Oĝuz and F. Ercan, A Genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Journal of Scheduling 8, pp. 323-351, 2005.

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

- Computation theory
- Conditioning Monitoring
- Controllers
- Global optimization
- Image Recognition
- Information Visualization
- Internet computing
- Machines
- Mathematical optimization
- Mechatronics and Robotics
- Modeling and Simulation
- Network
- Parallel Processing
- Power System
- Signal Processing
- Simulator
- Soft Computing and Computational Intelligent
- Software design
- Statistics
- Technology
- Ubiquitous Computing
- Wireless Sensor

- Total views:
**11827** - [From(publication date):

June-2010 - Dec 11, 2019] - Breakdown by view type
- HTML page views :
**8043** - PDF downloads :
**3784**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20