The Two-Machine Open Shop without Time Delays 

The Two-Machine Open Shop without Time Delays:

Experimental study:

In order to compare the running time of the two algorithms, we run GS algorithm and the new version of LAPT algorithm on the same input data. Due to the fact that both algorithms produce optimal solutions, we only care about their running times. The conducted experiment witnessed 6 stages, where the sizes of problem successively are 50, 100, 200, 500, 800, and 1000, as shown in Table 3.2. For each size, 10 sets of data were generated at random from [1,100]. Column 2 and column 3 of Table 3.2 present, for each size, average running times of GS and LAPT algorithms, respectively. The algorithm was implemented in Visual C++ 6.0 and the tests were run on a personnel computer with a 1.66 GHz Intel® Core™ Duo CPU on the MS Windows XP operating system. The results of the experiment are summarized in Table 3-2.

The Two-Machine Open Shop With Symmetric Time Delays:

In actual production runs, all kinds of consumptions are inevitable, such as the time consumed, the weight consumed, Man-made loss of goods brought and so on. in which time delays between the completion time of one job on one machine and the starting time on another machine are one of the most important losses. The time delays describe the waiting time between the completion of an operation and the beginning of the next operation of the same job.

The time delay between the completion of job k on machine i and its start on machine y is denoted by lrk. Now, if I jjk – I rk , we say that the time delays are symmetric, and if lljt = I jik , then the time delays are said to be job dependant. In this thesis, we restrict our study to the symmetric time delay case. Let us observe that in some applications, time delays might be larger than the processing times themselves. That is to say that we do not have choice than considering them, when building a solution. Most of open shop problems with time delays are NP-hard problems, even with unit-time operations and symmetric time delays [Yu, 1996]. In other words, it is difficult to discover an appropriate exact algorithm running in reasonable time, even for the simplest case. Let us illustrate this by the following example. In an airport, due to the influence of weather changes, breakdowns of machines, lack of fuel oil, passenger boarding delays and other factors, at a certain interval (for e.g. 10 minutes) the scheduling plan, based on the current situation, needs to be readjusted to avoid accidents, which poses the requirement that the algorithm should be prompt and accurate. Therefore, in many cases, we often employ heuristic algorithms which approach toward but not necessarily ensure the discovery of optimal solution., it needs a set of unified algorithm-evaluating criteria to judge the quality of algorithms, among which the worst-case analysis and the mean performance are the most frequently used criteria.

Lower Bounds:

The lower bound of a problem is the minimum value of the considered criterion that is the smallest makespan that can be obtained under ideal constraints. Different focuses on a problem may produce several different lower bounds for the problem. Whether in heuristic algorithms, meta- heuristic algorithms or exact algorithms, lower bounds play an important role. Indeed, for the heuristic approach, we usually use lower bounds to derive an upper bound on the error (either relative or absolute) of the optimal solution. In the meta heuristic approach, the lower bound might guide us either in the process of designing the meta-heuristic or in evaluating the solution processed to the lower bound which we have in hand. Finally, in the exact method, lower bounds might help us to either process to the optimality the partial solution at hand or ignore many partial solutions, whenever a branch and bound algorithm is used.

It is evident that the closer a lower bound is to the optimal solution, the more important role it will play. However, a lower bound is only a focus on one aspect of a problem. So, generally, the same problem includes several different lower bounds. In this section, we focus on the minimal time delay and see how to establish lower bounds. Let us first consider the special case of unit-time operations, before proceeding with the general case.

Heuristic approach:

Let us observe that most of open shop problems are NP-hard, and their optimal solutions are not always successfully obtained in reasonable time. In that case, we use heuristic algorithms to solve those problems. But at some point, we may not be satisfied with the solution of the current heuristic algorithm. We may then be interested to improve the quality of the solution. To do so, we may consider either the running time or the quality of the solution as the primary factor to improve. However, since the running time of most of heuristic algorithms is satisfactory, we mainly focus on the quality of the heuristic algorithm as the improvement criterion. Generally, this is evaluated through the quality of the worst case solution. In this section, first we present some worst-case results. Then, in the second step, an experimental study is conducted to compare two given heuristic algorithms.

Worst-case analysis:

The worst case analysis is to simulate and analyze the bound that can be reached under the worst circumstance. However, sometimes the result may be overly pessimistic. So, it does not necessarily comply with real situations, but provides feasible theoretical upper bound on the result produced by the heuristic algorithm.

Experimental study with unit-time operations
In this section, we deal with the problem of unit-time operations and symmetric time delays. We present two simple heuristics and compare their performance throughout an experimental study .

Meta-heuristic Algorithms:

For some special cases, heuristic algorithms can have some satisfactory results, but it is not universal. In other words, the heuristic algorithm can have a good result for a special problem, but not for all problems. Obviously, for each special problem, it is very troublesome and difficult to find out its corresponding algorithm. Therefore, some general heuristic algorithms are very important, and one of them is the meta-heuristic algorithm, which is a very famous method for solving a very general class of computational problems. A review of literature introduces meta-heuristic algorithms for solving the open shop problem. Tabu search, introduced by Glover [1989,1990, 1997], is a local search approach designed for solving hard combinatorial optimization problems. More refined versions and a large number of successful applications to improve heuristic algorithms can be found as follows: Liaw has worked extensively on the open shop problem, proposing a tabu search algorithm [1999a, 2003], simulated annealing [1999b], and hybrid genetic algorithm and search [2000]. Alcaide et al. [1997] present a tabu search algorithm for the minimum makespan of open shop problem. A promising hybrid (GA) heuristic approach for open-shop scheduling problems is published by Fang et al. [ 1994]. In this section, there will be an introduction on some general heuristic algorithms (meta heuristic), which may be used as a framework to design algorithms for solving general NP-hard problems. Although the framework is the same, if we can still make adjustments to improve significantly the efficiency of the resulting algorithm. The basic strategy of a meta-heuristic algorithm improvement (adjustement) includes the following criteria.

Stopping criterion
Stopping criterion does not depend on the algorithm details (framework). It is used to avoid unnecessary costs. Generally, stopping criteria are as follows:
a) The qualified result has been found; for example, the result is equal to the lower bound.
b) It takes too long. For example: the algorithm enters into a deadlock.
c) The possibility of the result improvement is too low.

Internal Structure: Each meta-heuristic algorithm has its own formwork which includes initial value, special parameters, neighborhood structure and so on. Intensification and diversification module is also the key point for the improvement of meta-heuristic algorithms.

Hybrid algorithm: If it is difficult for the meta-heuristic algorithms to break the shackles, combining the advantages of different algorithms to create a new hybrid algorithm is a prevailing practice. In this dissertation, we mainly introduce the improvement of two meta heuristic algorithms (tabu search and simulated annealing) for the two-machine open shop problem with time delays .

Internal Structure:

As far as meta-heuristic algorithms are concerned, despite the fact that they all have their own frameworks and parameters, they also share some common points. For example, the value ranges of most meta-heuristic algorithms are in whole domain, so the strategies of intensification and diversification both can be made use of to conduct further exploration and exploitation on value taking. Therein, the idea of intensification is to thoroughly explore more of the current solution in order to find the global best solution. The idea of diversification is to force to search the previously unexplored areas of the search space in order to avoid local convergence.

Experimental Results With The Hybrid Algorithm
At first, we generate a random initial sequence. Initial temperature To is 600. Terminated temperature T i is 0.01. The cooling factor is 0.95; the size of the tabu list is N/2. The conducted experiment witnessed 4 stages, where the sizes of the problem successively are 20, 50, 100, and 200. For each size, 10 sets of data were generated at random from [1,100]. The second column represents the average time of execution. The average, the best, and the worst makespan are illustrated by the third, fourth and fifth column, respectively.

General Conclusion:

The problem we have studied in this thesis is the two-machine open shop problem with time delays. The open shop scheduling problem has a much larger solution space than the job shop or flow shop scheduling problems because, as for the open shop model, no restrictions are placed on the processing order on the jobs. But little attention is paid to it by researchers and practitioners, primarily because of the limitation of traditional applications. In recent years, with technology innovation and scientific management, the open shop scheduling model began to come under an increasing attention, as it can be seen from the growth rate of relevant studies published. This demonstrates that more importance will be attached to this problem in the future.

Table des matières

Chapter 1 General Introduction 
Chapter 2 Scheduling Problems 
2.1 Introduction
2.2. Scheduling models
2.3 Basic Definitions
2.4 Three-Field Notation
2.5 Gantt Chart
2.6 Scheduling with time delays
2.7 A Brief introduction to the complexity theory
2.8 Analysis of Scheduling Problems
2.8.1 Exact methods
2.8.2 Relaxation
2.8.3 Pseudo-Polynomial Algorithms
2.8.4 Approximation Algorithms
2.8.4.1 Analytic Approach
2.8.4.2 Experimental Approach
2.9 Description Of An Exact And A Heuristic Approach
2.9.1 Exact Algorithms
2.9.2 Heuristic Algorithms
2.9.3 Meta-heuristic Algorithms
2.9.3.1 Simulated Annealing
2.9.3.2 Genetic Algorithms
2.9.3.3 Tabu search method
Chapter 3_The Two-Machine Open Shop without Time Delays 
3.1 Introduction
3.2 Gonzalez-Sahni Algorithm
3.3 Pinedo-Schrage algorithm
3.3.1 Experimental study
Chapter 4 The Two-Machine Open Shop With Time Delays
4.1 Introduction
4.2 Lower Bounds
4.2.1 Unit-time operations
4.2.2 General processing times
4.3 Heuristic approach
4.3.1 Worst-case analysis
4.3.2 Experimental study with unit-time operations
4.4 Meta-heuristic Algorithms
4.4.1 Internal Structure
4.4.1.1 Simulated-Annealing
1. Basic algorithm
2. Improvement experiments
4.4.1.2 Tabu search
1 Basic algorithm
2.1mprovement experiments
4.4.2 A Hybrid Algorithm
4.4.2.1 Basic idea of the hybrid algorithm
4.4.2.2. Experiment Results With The Hybrid Algorithm
General Conclusion

Télécharger le rapport complet