No description available.

Reactive repair of a disrupted schedule is a better alternative to total rescheduling, as the latter is a time consuming process and also results in shop floor nervousness. The schedule repair heuristics reported in the literature generally address only machine breakdown. This paper presents a modified Affected Operations Rescheduling (mAOR) approach, which deals with many of the disruptions that are frequently encountered in a job shop. The repair of these disruptions has been decomposed into four generic repair actions that can be applied singularly or in combination. These generic repair actions are evaluated through a simulation study with the performance measures of efficiency and stability. The results indicate the effectiveness of the mAOR heuristic in dealing with typical job shop disruptions. / Singapore-MIT Alliance (SMA)

Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure.

Les travaux de recherche proposés dans cette thèse portent sur les problèmes d'ordonnancement rencontrés dans les systèmes de production automatisés en prenant en compte des contraintes telles que l'absence d'espace de stockage entre les machines et la flexibilité des ressources. Plus particulièrement, nous avons étudié les problèmes d'ordonnancement de job-shops classiques et hybrides soumis à des contraintes de blocage particulières avec comme objectif la minimisation du temps total d'opération. Dans un premier temps, nous avons modélisé les problèmes d'ordonnancement de type job-shop (classique et flexible) avec la contrainte de blocage particulière afin d'obtenir une solution exacte. Pour les problèmes de taille plus importante, il n'était pas possible d'obtenir une solution exacte à ce problème en un temps raisonnable. Par conséquent, nous avons développé des bornes inférieures complémentaires. Dans le cas du job shop classique, une méta-heuristique basée sur l'algorithme de recuit simulé pour résoudre le problème étudié a été proposée. Pour développer un voisinage efficace, nous avons donné une méthode qui permet de détecter les conflits qui peuvent survenir après la modification des séquences. Des résultats d'expérimentations réalisés sur des instances de petites et moyennes tailles montrent l'efficacité de bornes inférieures ainsi que l'heuristique développée / The research in this thesis ; focus on the scheduling problems encountered in automated production systems and takes into account new constraints, such as buffer stocks of limited capacity, flexibility of resources, etc.. Two main objectives are set, namely the proposal of new models of scheduling, development of approaches and lower bounds for scheduling systems studied (classical job shop and hybrid job shop with blocking Rcb). The lower bounds are developed for the problems of job-shop classic and hybrid with Rcb blocking constraint. Heuristics based on simulated annealing have been developed for the job-shop problems subject to the Rcb blocking constraint. Results of experiments conducted on instances of small and medium sizes show the effectiveness of lower bounds and heuristics developed

Disruptions to job shop schedules are tedious and difficult to incorporate after the schedule has been generated and implemented on the shop floor. In order to deal with such disruptions, a real time reactive scheduling strategy is essential. Reactive scheduling is the process of repairing the predictive schedule during online execution for internal disruptions (e.g. machine breakdowns) and external deviations (e.g. prepone or postpone of orders). Existing approaches for schedule repair in real time mainly utilize heuristics such as Right Shift Rescheduling (RSR), and Affected Operation Rescheduling (AOR). In the present form, both these approaches are only used for handling machine breakdowns in the shop floor, but are inept in accommodating new and unexpected job orders. These approaches also neglect specific issues related to urgent jobs, for instance multiple job routings during the repair of the schedule. In this paper the existing heuristics (RSR and AOR) have been modified to include urgent jobs. Also a modified AOR approach (mAOR) is proposed that considers urgent jobs with multiple job routings. An extensive simulation study has been conducted on a job shop simulation testbed for the efficiency and stability of the repaired schedule using the mAOR and RSR heuristics. The efficiency of the repaired schedule is a measure of the percentage change in the makespan after incorporating repairs whereas the stability of the schedule is a function of starting time deviations that indicate the degree by which it deviates from the original schedule. The results of the experiments indicate significant benefits of the modified AOR algorithm over the existing RSR schedule repair heuristic. / Singapore-MIT Alliance (SMA)

Flexible job-shop scheduling problem (FJSP) is a generalization of the classical job-shop scheduling problem (JSP). It takes shape when alternative production routing is allowed in the classical job-shop. However, production scheduling becomes very complex as the number of jobs, operations, parts and machines increases. Until recently, scheduling problems were studied assuming that all of the problem parameters are known beforehand. However, such assumption does not reflect the reality as accidents and unforeseen incidents happen in real manufacturing systems. Thus, an optimal schedule that is produced based on deterministic measures may result in a degraded system performance when released to the job-shop. For this reason more emphasis is put towards producing schedules that can handle uncertainties caused by random disruptions. The current research work addresses solving the deterministic FJSP using evolutionary algorithm and then modifying that method so that robust and/or stable schedules for the FJSP with the presence of disruptions are obtained. Evolutionary computation is used to develop a hybridized genetic algorithm (hGA) specifically designed for the deterministic FJSP. Its performance is evaluated by comparison to performances of previous approaches with the aid of an extensive computational study on 184 benchmark problems with the objective of minimizing the makespan. After that, the previously developed hGA is modified to find schedules that are quality robust and/or stable in face of random machine breakdowns. Consequently, a two-stage hGA is proposed to generate the predictive schedule. Furthermore, the effectiveness of the proposed method is compared against three other methods; two are taken from literature and the third is a combination of the former two methods. Subsequently, the hGA is modified to consider FJSP when processing times of some operations are represented by or subjected to small-to-medium uncertainty. The work compares two genetic approaches to obtain predictive schedule, an approach based on expected processing times and an approach based on sampling technique. To determine the performance of the predictive schedules obtained by both approaches with respect to two types of robustness, an experimental study and Analysis of Variance (ANOVA) are conducted on a number of benchmark problems.

Flexible job-shop scheduling problem (FJSP) is a generalization of the classical job-shop scheduling problem (JSP). It takes shape when alternative production routing is allowed in the classical job-shop. However, production scheduling becomes very complex as the number of jobs, operations, parts and machines increases. Until recently, scheduling problems were studied assuming that all of the problem parameters are known beforehand. However, such assumption does not reflect the reality as accidents and unforeseen incidents happen in real manufacturing systems. Thus, an optimal schedule that is produced based on deterministic measures may result in a degraded system performance when released to the job-shop. For this reason more emphasis is put towards producing schedules that can handle uncertainties caused by random disruptions. The current research work addresses solving the deterministic FJSP using evolutionary algorithm and then modifying that method so that robust and/or stable schedules for the FJSP with the presence of disruptions are obtained. Evolutionary computation is used to develop a hybridized genetic algorithm (hGA) specifically designed for the deterministic FJSP. Its performance is evaluated by comparison to performances of previous approaches with the aid of an extensive computational study on 184 benchmark problems with the objective of minimizing the makespan. After that, the previously developed hGA is modified to find schedules that are quality robust and/or stable in face of random machine breakdowns. Consequently, a two-stage hGA is proposed to generate the predictive schedule. Furthermore, the effectiveness of the proposed method is compared against three other methods; two are taken from literature and the third is a combination of the former two methods. Subsequently, the hGA is modified to consider FJSP when processing times of some operations are represented by or subjected to small-to-medium uncertainty. The work compares two genetic approaches to obtain predictive schedule, an approach based on expected processing times and an approach based on sampling technique. To determine the performance of the predictive schedules obtained by both approaches with respect to two types of robustness, an experimental study and Analysis of Variance (ANOVA) are conducted on a number of benchmark problems.

Within manufacturing systems, process planning and scheduling are two interrelated problems that are often treated independently. Process planning involves deciding which operations are required to produce a finished product and which resources will perform each operation. Scheduling involves deciding the sequence that operations should be processed by each resource, where process planning decisions are known a priori. Integrating process planning and scheduling offers significant opportunities to reduce bottlenecks and improve plant performance, particularly for complex job shops. This research is motivated by the coating and laminating (CandL) system of a film manufacturing facility, where more than 1,000 product types are regularly produced monthly. The CandL system can be described as a complex job shop with sequence dependent setups, operation re-entry, minimum and maximum wait time constraints, and a due date performance measure. In addition to the complex scheduling environment, products produced in the CandL system have multiple feasible process plans. The CandL system experiences significant issues with schedule generation and due date performance. Thus, an integrated process planning and scheduling approach is needed to address large scale industry problems. In this research, a novel proxy measure based local search (PBLS) approach is proposed to address the integrated process planning and scheduling for a complex job shop. PBLS uses a proxy measure in conjunction with local search procedures to adjust process planning decisions with the goal of reducing total tardiness. A new dispatching heuristic, OU-MW, is developed to generate feasible schedules for complex job shop scheduling problems with maximum wait time constraints. A regression based proxy approach, PBLS-R, and a neural network based proxy approach, PBLS-NN, are investigated. In each case, descriptive statistics about the active process plan set are used as independent variables in the model. The resulting proxy measure is used to evaluate the effect of process planning local search moves on the objective function sum of total tardiness. Using the proxy measure to guide a local search reduces the number of times a detailed schedule is generated reducing overall runtime. In summary, the proxy measure based local search approach involves the following stages: • Generate a set of feasible schedules for a set of jobs in a complex job shop. • Evaluate the parameters and results of the schedules to establish a proxy measure that will estimate the effect of process planning decisions on objective function performance. • Apply local search methods to improve upon feasible schedules. Both PBLS-R and PBLS-NN are integrated process planning and scheduling heuristics capable of addressing the challenges of the CandL problem. Both approaches show significant improvement in objective function performance when compared to local search guided by random walk. Finally, an optimal solution approach is applied to small data sets and the results are compared to those of PBLS-R and PBLS-NN. Although the proxy based local search approaches investigated do not guarantee optimality, they provide a significant improvement in computational time when compared to an optimal solution approach. The results suggest proxy based local search is an appealing approach for integrated process planning and scheduling in complex job shop environment where optimal solution approaches are not viable due to processing time. / Ph. D.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura. / The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.