Summary On
A Mathematical Programming Model for Flow Shop Scheduling Problems for Considering Just in Time Production.
R. Ramezanian, M.B. Aryanezhad & M. Heydari*
R. Ramezanian: MSc in Department of Industrial Engineering, Iran University of Science and Technology.
M.B. Ariyanezhad: Professor in Department of Industrial Engineering, Iran University of Science and Technology.
M. Heydari: Assistant Professor in Department of Industrial Engineering, Iran University of Science and Technology.
Introduction
This paper is primarily concerned with industrial scheduling problems, where one has to sequence the jobs on each resource over time.
In a flow shop environment, a set of jobs must be processed on a number of sequential machines, processing routes of all jobs are the same, that is the operations of any job are processed in the same order, whereas a flow shop with bypass model, a generalization of the ordinary flow shop model, is more realistic, and it assumes that at least one job does not visit one machine.
This is the scheduling of n jobs in a m machine flow shop, where some jobs do not require processing on the some machines. The objective is to minimize the sum of earliness and tardiness costs. Just in time concept for the scheduling environment can be provided by considering minimization of the sum of earliness and tardiness costs as the objective function.
Problem Description
The FSSP with bypass can be described as follows: Each of n jobs from set J={1,2,..., n} will be sequenced through m machines (i=1, 2,...,m). Job has a sequence of lj operations through a subset m machines (jobs may have zero processing time on some machines) and a given due date dj.
Mathematical Formulation
The Genetic Algorithm
Genetic algorithms have been proven to be powerful techniques for constrained optimization and
combinatorial optimization problems.
The GA was proposed by Holland (1975) [15] to encode the factors of a problem by chromosomes, where each gene represents a feature of the problem. The GA’s structure and parameter setting affect its performance.
The overall structure of our GA can be described as follows:
1. Coding: The genes of the chromosomes describe the jobs, and the order in which they appear in the chromosome describes the sequence of Jobs. Each chromosome represents a solution for the problem.
2. Initial population: The initial chromosomes are obtained by a Random dispatching rule for sequencing.
3. Fitness evaluation: The sum of earliness and tardiness cost is computed for each chromosome in the current generation.
4. Selection: In any iteration, chromosomes are chosen randomly for crossover and mutation.
5. Offspring generation: The new generation is obtained by changing the sequencing of operations (reproduction, enhanced order crossover and mutation). These rules preserve feasibility of new individuals. New individuals are generated until a fixed maximum number of individuals is reached.
6. Stop criterion: Fixed number of generations is reached. If the stop criterion is satisfied, the algorithm ends and the best chromosome, together with the corresponding schedule, are given as output. Otherwise, the algorithm iterates again steps 3–5.
Based on bypass consideration GA is adapted to consider operation with zero processing time on some machines.
Conclusions
In this paper, we presented a mathematical formulation model for minimizing sum of the earliness and tardiness costs in flow shop scheduling problem with bypass consideration (some jobs may not process on some machines) which is often occurring in shop environment of real world. We proposed genetic algorithm to solve this problem with medium and large size. Computational experiments have been performed to demonstrate that the proposed GA is efficient and flexible.
A Mathematical Programming Model for Flow Shop Scheduling Problems for Considering Just in Time Production.
R. Ramezanian, M.B. Aryanezhad & M. Heydari*
R. Ramezanian: MSc in Department of Industrial Engineering, Iran University of Science and Technology.
M.B. Ariyanezhad: Professor in Department of Industrial Engineering, Iran University of Science and Technology.
M. Heydari: Assistant Professor in Department of Industrial Engineering, Iran University of Science and Technology.
Introduction
This paper is primarily concerned with industrial scheduling problems, where one has to sequence the jobs on each resource over time.
In a flow shop environment, a set of jobs must be processed on a number of sequential machines, processing routes of all jobs are the same, that is the operations of any job are processed in the same order, whereas a flow shop with bypass model, a generalization of the ordinary flow shop model, is more realistic, and it assumes that at least one job does not visit one machine.
This is the scheduling of n jobs in a m machine flow shop, where some jobs do not require processing on the some machines. The objective is to minimize the sum of earliness and tardiness costs. Just in time concept for the scheduling environment can be provided by considering minimization of the sum of earliness and tardiness costs as the objective function.
Problem Description
The FSSP with bypass can be described as follows: Each of n jobs from set J={1,2,..., n} will be sequenced through m machines (i=1, 2,...,m). Job has a sequence of lj operations through a subset m machines (jobs may have zero processing time on some machines) and a given due date dj.
Mathematical Formulation
- The objective function (1) considers the minimization of the earliness cost and the tardiness cost and the considered objective function provides just in time production in manufacturing systems.
- The constraint set (2) determines earliness and tardiness of each job.
- The constraint set (3) corresponds to the computation of the completion time of job (if job j is not processed on machine i, its completion time is the same as completion time on previous machine).
- The constraint set (4) forces to start the processing of each job only when it has been completed on the precedent machine.
- The constraint set (5) forces to start the processing of each job only when its precedent job has been completed on the same machine.
- The constraint sets (6-11) determine sequence of jobs for any machine. The constraint set (12) bounds the job starting times to be after job release times in the system.
- The constraint set (13) insures that the job finishing times on the first machine to be after job release times (if job j does not require processing on the first machine,
- C1j=Rj. (14) is logical constraint.
The Genetic Algorithm
Genetic algorithms have been proven to be powerful techniques for constrained optimization and
combinatorial optimization problems.
The GA was proposed by Holland (1975) [15] to encode the factors of a problem by chromosomes, where each gene represents a feature of the problem. The GA’s structure and parameter setting affect its performance.
The overall structure of our GA can be described as follows:
1. Coding: The genes of the chromosomes describe the jobs, and the order in which they appear in the chromosome describes the sequence of Jobs. Each chromosome represents a solution for the problem.
2. Initial population: The initial chromosomes are obtained by a Random dispatching rule for sequencing.
3. Fitness evaluation: The sum of earliness and tardiness cost is computed for each chromosome in the current generation.
4. Selection: In any iteration, chromosomes are chosen randomly for crossover and mutation.
5. Offspring generation: The new generation is obtained by changing the sequencing of operations (reproduction, enhanced order crossover and mutation). These rules preserve feasibility of new individuals. New individuals are generated until a fixed maximum number of individuals is reached.
6. Stop criterion: Fixed number of generations is reached. If the stop criterion is satisfied, the algorithm ends and the best chromosome, together with the corresponding schedule, are given as output. Otherwise, the algorithm iterates again steps 3–5.
Based on bypass consideration GA is adapted to consider operation with zero processing time on some machines.
Conclusions
In this paper, we presented a mathematical formulation model for minimizing sum of the earliness and tardiness costs in flow shop scheduling problem with bypass consideration (some jobs may not process on some machines) which is often occurring in shop environment of real world. We proposed genetic algorithm to solve this problem with medium and large size. Computational experiments have been performed to demonstrate that the proposed GA is efficient and flexible.
No comments:
Post a Comment