The paper gives analysis of the benefits of using load balancing of machines in scheduling. The paper is organized as follows. In Section 2, the job shop problem is intro- duced together with the objectives and constraints. Section 3 illustrates the job shop scheduling algorithm, while Section 4 describes the genetic algorithm for load balanc- ing. The real-world scheduling problem in a printing company is explained in Section 5 with experimental results obtained on real-world data, followed by conclusions in Section 6.
A working centre Wc consists of identical and non-identical machines. Identical machines denote ma- chines, which have the same characteristics. Each job is assigned a release date r j , i. The processing of job J j on machine M i is referred to as operation represented by an order pair i,j , with the processing time denoted by p. Precedence constraints are imposed on the order of operation ij processing.
Operation processing times are imprecise due to machine and human fac- tors. For example, we can estimate that the processing time of an operation is not shorter than a, not longer than c, but most likely it takes b time units.
Jobs are of different types and are grouped into F families on the basis of their processing requirements. Very often it is not possible to meet the due date for all the jobs. In order to de- liver at least part of the job to the customer, the scheduler can decide to split up the job into lots. Each operation is allocated to a machine from the specified work-centre, before the sequencing of operations on the machine takes place.
Phase 1. Lots determination: for each job a decision whether to split it up into lots is made together with the size of lots. Phase 2. Phase 3. The focus of this paper is on phase 2. Phases 1 and 3 will be described briefly in the remainder of this section while the description of machine load balancing will be given in Section 4. A fuzzy if-then rule-based system was developed which decides on splitting-up of jobs and the size of each lot.
Initially, lots are of the same size. Fuzzy if-then rules determine the change of the lot expressed by the linguistic variables, Large Negative, Medium Negative, Small, Medium Positive and Large Positive using the values of linguistic variables workload of the shop floor, size of the job, and the urgency of the job.
The developed rule-based system for lot sizing is given in detail in Petrovic et al, Imprecise processing times of operations and due dates are mod- eled by fuzzy sets. Satisfaction grades are introduced for each objective to reflect the decision maker preferences to the achieved values of the objectives.
Values of the ob- jectives are mapped into satisfaction grades, which take values from the interval [0, 1], where 0 represents full dissatisfaction and 1 full satisfaction with the achieved ob- jective value. An average of the satisfaction grades of all objectives is used as the fit- ness function F in the developed genetic algorithm to evaluate the quality of solutions schedules. A genetic algorithm is an iterative search procedure, which was successfully used in a variety of combinato- rial optimization problems Reeves, A genetic algorithm maintains iteratively a population of solutions, each solution being represented by a chromosome.
The fit- ness of the solution is determined by the value of the objective function achieved by the solution. The solutions with higher fitness have better chances to survive to the next iteration called generation.
The solutions are changed from iteration to iteration by applying crossover operators, which combine two chromosomes to obtain off- springs and mutation operator, which modifies a single chromosome. The main char- acteristics of the developed genetic algorithm are described below. Initialisation: The algorithm which generates initial solutions distinguishes two cases: when the number of lots of a job is smaller or equal, and larger than the number of machines.
In the first case, lots of a single job to be processed in the work-centre are allocated in a random order to the identical machines in such a way so that no ma- chine processes more than one lot of the same job.
In the second case, the lots are al- located to the different identical machines. When all machines are used in allocation, then for each remaining lot, the current workload of the machines are calculated and the machine of the lowest workload is chosen. Chromosome representation: Each chromosome represents allocation of lots to machines using two layers, shown in Figure 1.
First layer contains job identification number and the number of lots the job is split into. The number of lots determines the number of elements in the second layer. Remember me on this computer. Enter the email address you signed up with and we'll email you a reset link. Need an account? Click here to sign up. Download Free PDF. Yan-chun Liang.
A short summary of this paper. In the context of proposed algorithm, a clonal selection based hyper mutation and a life span extended strategy is designed. During the search process, an adaptive penalty function is designed so that the algorithm can search in both feasible and infeasible regions of the solution space.
Simulated experiments were conducted on 23 benchmark instances taken from the OR-library. The results show the effectiveness of the proposed algorithm. Introduction The job shop scheduling problem JSSP is one of the most well-known problems in both fields of production management and combinatorial optimization.
The classical n-by-m JSSP studied in this paper can be described as follows: scheduling n jobs on m machines with the objective to minimize the completion time for processing all jobs. Each job consists of m operations with predetermined processing sequence on specified machines and each o peration of the n jobs needs an uninterrupted processing time with given length. Operations of the same job cannot be processed concurrently and each job must be processed on each machine exactly once.
Efficient methods for solving JSSP are important for increasing production efficiency, reducing cost and improving product quality. Moreover, JSSP is acknowledged as one of the most challenging NP-hard problems [1] and there is no any exact algorithm can be employed to solve JSSP consistently even when the problem scale is small. So it has drawn the attention of researches because of its theoretical, computational, and empirical significance since it was introduced. Due to the complexity of JSSP, exact techniques, such as branch and bound [2, 3], and dynamic programming [4, 5] are only applicable to modest scale problems.
Most of them fail to obtain good solutions solving large scale problems because of the huge memory and lengthy computational time required. On the other hand, heuristic methods, include dispat ching priority rules [], shifting bottleneck approach [] and Lagrangian relaxation [], are attractive alternatives for large scale problems.
With the emergence of new techniques from the field of artificial intelligence, much attention has been devoted to meta-heuristics.
One main class of meta-heuristics is the construction and improvement heuristic, such as tabu search [15 - 17] and simulated annealing [18, 19]. Another main class of meta-heuristic is the population based heuristic. Successful examples of population based algorithms include genetic algorithm GA [], particle swarm optimization PSO [23, 24], artificial immune system and their hybrids [], and so on.
Among the above methods, GA, proposed by John Holland [28, 29], is reg arded as problem independent approach and is well suited to dealing with hard combinational problems. Classical GAs use binary strings to represent potential solutions. Another problem in classical GAs is premature convergence. From the view point of the JSSP itself, it is a hard combinatorial optimization problem with constraints.
The goal of the scheduling methods is to find a solution that satisfies the constraints. However, some of the infeasible solutions are of similarity with the feasible optimal solutions, and may provide useful information for generating optimal solution. If we search only within the feasible regions, the generation of the optimal schedule not only requires long time but also decreases the possibility to obtain the optimal solution.
Motivated by these perspectives, we proposed a novel genetic algorithm which adopts an operation based representation and a novel search scheme. The proposed genetic algorithm searches in both feasible and infeasible regions. In the proposed algorithm, the potential solutions are generated without considering the constraints. To handle the infeasible solutions, we proposed an adaptive penalty function to impose penalties on the evaluation functions.
The remainder of this paper is organized as follows. Section 2 briefly introduces the genetic algorithms, and then proposes the modified genetic algorithm.
Section 3 first introduces the basic penalty function, and then proposes the dynamic and adaptive penalty function. In Section 4, the implementation of proposed algorithm is presented. In Sectio n 5, the corresponding computational and comparative results are given. Finally, conclusion remarks are given in Section 6.
The modified genetic algorithm 2. During the searching process, the selection, crossover and mutation operators are executed repeatedly until the stop criteria is satisfied. The flow chart of the classical genetic algorithm is shown in Fig.
Y Output Figure 1. Flow chart of the classical genetic algorithm. The quality of the chromosome is evaluated by the fitness value. Generally speaking, the chromosomes with higher fitness value have higher probability to generate child chromosomes.
Thus, the selection rate is in accordance with the fitness value of each chromosome. But if we still select parent chromosomes according to the fitness value for crossover a nd mutation operations, the chromosomes with similar scheme will be added to the population again and again, and the pseudo-optimal chromosomes will occupy the whole population at last.
Crossover exchange parts of genes of two parent chromosomes to generate new chromosomes. The mutation operator changes genes in a variable region of the chromosome. The mutation operator keeps the diversity of the population and introduces features that are not present in the current population, therefore prevent premature convergence.
But the crossover and mutation operators cannot work well when the pseudo-optimal individual dominates the whole population. Crossover operator uses parent chromosomes to produce child chromosomes, thus the child chromosomes have the same schemes with their parents. Mutation operator is a random process, if we perform high mutation rate, most of the chromosomes may become non-function or develop into harmful specificities; on the other hand, if we perform low mutation rate, the new introduced chromosome will soon be eliminated by the selection strategy because of the domination of the pseudo-optimal chromosomes.
Modified genetic algorithm Based on the above discussions, the classical genetic algorithm cannot escape premature convergence consistently if the pseudo-optimal individual dominates the whole population. In this paper, we address two operations, one is the clonal selection based hypermutation, and the other is the lifespan extended strategy.
The idea of these two operations is based on two observations. Firstly, to prevent premature convergence when the pseudo-optimal chromosomes dominate the whole population, chromosomes with high diversity are needed. Secondly, the new introduced chromosomes should have high diversity, but if they cannot compete with the pseudo-optimal chromosomes, they will be eliminated soon, thus, the diversified chromosomes should also have high fitness values.
Clonal selection based hyper mutation According to the theory of clonal selection [30, 31], when animals are exposed to antigens, some of its bone marrow derived a kind of cells, named B lymphocytes. The B lymphocytes can recognize the antigen with certain affinity. These B lymphocytes will be stimulated to proliferate and mature into terminal antibody secreting cells. Proliferation of B lymphocytes is an asexual and amitotic process, which creates a set of clones identical to the parent B lymphocytes.
And the proliferation rate is in direct proportion to affinity, i. During proliferation, the clones undergo a hyper mutation, which diversifies the repertoire of the antigen-activated B cells. The receptor edit guides the process of proliferation hyper mutation which results in the B cells with high affinity survived. Motivated by the clonal selection theory, the proposed clonal selection based hyper mutation operation can be described as follows. First, setup a clonal library, and then the elite chromosomes in the population are copied to the clonal library.
After this, the elite chromosomes repeatedly reproduce themselves until the clonal library is full. Then the chromosomes in the clonal library undergo a high rate mutation. At last, replace the worst chromosomes in the population by the best chromosomes in the clonal library. By the clonal selection based hyper mutation, the new generated chromoso mes either have higher fitness value in competence with the pseudo-optimal and higher diversity.
Thus the algorithm has a higher probability to escape from the pseudo-optimal trap. The i-th element of the vector records the survival time of the i-th chromosomes in the population. The update strategy only replaces the individuals that survived longer than a fix time period. By the lifespan extending strategy, the new introduced chromosomes can not be eliminated soon after introduced.
During the extended lifespan, they mature and can compete with other pseudo-optimal chromosomes. Calculate fitness value f of each individual chromosome. Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer-Integrated Manufacturing , 18 3—4 , — Mesghouni, K.
Evolution programs for job-shop scheduling. In Systems, man, and cybernetics, Computational cybernetics and simulation. Nouiri, M. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem.
Pezzella, F. A genetic algorithm for the flexible job-shop scheduling problem. Tay, J. An effective chromosome representation for evolving flexible job shop schedules. Deb Ed. New developments in scheduling applications. Tung-Kuan, L. Developing a multiobjective optimization scheduling system for a screw manufacturer: A refined genetic algorithm approach.
IEEE Access , 2 , — Watanabe, M. A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Yilmaz Eroglu, D. MIP models and hybrid algorithms for simultaneous job splitting and scheduling on unrelated parallel machines. Zhang, G. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications , 38 4 , — Scheduling jobs with variable job processing times on unrelated parallel machines.
Download references. You can also search for this author in PubMed Google Scholar. Correspondence to Tung-Kuan Liu. Reprints and Permissions. Chang, HC. Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms.
J Intell Manuf 28, — Download citation. Received : 22 November Accepted : 17 April Published : 28 April Issue Date : December Anyone you share the following link with will be able to read this content:. Sorry, a shareable link is not currently available for this article. Provided by the Springer Nature SharedIt content-sharing initiative. Skip to main content.
Search SpringerLink Search. Abstract In contrast to traditional job-shop scheduling problems, various complex constraints must be considered in distributed manufacturing environments; therefore, developing a novel scheduling solution is necessary. References AitZai, A. Article Google Scholar Chan, F.
0コメント