In this paper we propose an improved algorithm to search optimal solutions to the single machine total weighted tardiness scheduling problem. We propose using longest common sequence to combine with the random key method. Numerical simulation shows that the scheme we proposed could improve the search efficiency of genetic algorithm in this problem for some cases.

A hybrid methodology of game theory and Monte Carlo Tree Search was developed and the hybrid methodology was tested with various case studies through the nurse scheduling problem to show that it was able to form Pareto front dominance solutions, finding feasible solutions that were optimal and finding feasible partial solutions in over-constrained problems. The performance comparison was carried out with the Genetic Algorithm on the Resident Physician Scheduling problem and showed that the hybrid methodology was able to produce better quality solutions compared to the state of the art approach.

International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / The Broadcast Scheduling Problem (BSP) is a well known NP-complete problem that arises in the study of wireless networks. In the BSP, a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. The objective is a collision free transmission schedule with the minimum number of TDMA slots and maximal slot utilization. Such a schedule will minimize the total system delay. We present variations of a Greedy Randomized Adaptive Search Procedure (GRASP) for the BSP. Path-relinking, a post-optimization strategy is applied. Also, a reactivity method is used to balance GRASP parameters. Numerical results of our research are reported and compared with other heuristics from the literature.

The flow shop scheduling problems with fuzzy processing times and fuzzy due dates are investigated in this paper. The concepts of earliness and tardiness are interpreted by using the concepts of possibility and necessity measures that were developed in fuzzy sets theory. And the objective function will be taken into account through the different combinations of possibility and necessity measures. The genetic algorithm will be invoked to tackle these objective functions. A new idea based on longest common substring will be introduced at the best-keeping step. This new algorithm reduces the number of generations needed to reach the stopping criterion. Also, we implement the algorithm on CUDA. The numerical experiments show that the performances of the CUDA program on GPU compare favorably to the traditional programs on CPU.

The job scheduling problem is a type of scheduling problem where a list of jobs and machines are given. A solution consists of a schedule where each job is assigned to one or multiple machines at a certain time. In this study, a multiobjective evolutionary algorithm called NSGA-II was applied to optimize schedules for a particular scheduling problem given by a board game made by the Swedish educative company INSU. The scheduling problem features novel restrictions on the schedules, such as transportation delay between the jobs, skill requirements for the machines to fulfill. The board game also allows pre-emption, i.e., that the jobs can be paused and resumed by the same or other machines. These restrictions impose a challenge for creating a genetic representation for the evolutionary algorithm and a decoder which decodes the representation into a schedule. This problem was solved by proposing a new genetic representation based on previous work and testing it with a few crossover and mutation methods in two experiments. The experiments found that the new representation is effective in creating high-quality schedules, but it is inconclusive as to which crossover and mutation method is the most effective. The decoder’s execution time was also measured, which showed that the decoder scales rapidly with an increasing number of jobs. Despite this, the new representation and decoder are useful for optimizing other scheduling problems with pre-emption and other restrictions.

<p>We are given a sequence of jobs on a single machine, and each job has a weight, processing time and a due date. A job is early when it finishes before or on its due date and its earliness is the amount of time between its completion time and its due date. A job is tardy when it finishes after its due date and its tardiness is the amount of time between its due date and its completion time. The TWET problem is to find a schedule which minimizes the total weighted earliness and tardiness. We are focusing on the TWET problem with a constant number of distinct due dates and polynomially related weights. This problem has been proven to be NP-hard. In this thesis, we present a dynamic programming algorithm for our TWET problem first and then convert it into an FPTAS by adopting a rounding scheme.</p> <p>There are several important points in our algorithm: we observe the importance of the straddlers and guess them at the beginning through exhaustive enumeration, and insert them back at the very end by solving a linear problem; we know a series of structural properties of the optimal schedule to shrink the state space of the DP; we increase each due date to get a new problem and adopt a rounding scheme of the DP for the new problem to avoid preemption. Finally we move the due dates back to get the final schedule for the original TWET problem without changing the objective value much.</p> / Master of Science (MSc)

Yes / In this paper we study a complex real world workforce scheduling problem. We apply constructive search and variable neighbourhood search (VNS) metaheuristics and enhance these methods by using a variable fitness function. The variable fitness function (VFF) uses an evolutionary approach to evolve weights for each of the (multiple) objectives. The variable fitness function can potentially enhance any search based optimisation heuristic where multiple objectives can be defined through evolutionary changes in the search direction. We show that the VFF significantly improves performance of constructive and VNS approaches on training problems, and "learn" problem features which enhance the performance on unseen test problem instances.

A generalized dynamic programming based algorithm and a local search heuristic are used to solve the Two Runway Departure Scheduling Problem that arises at an airport. The objective of this work is to assign the departing aircraft to one of the runways and find a departing time for each aircraft so that the overall delay is minimized subject to the timing, safety, and the ordering constraints. A reduction in the overall delay of the departing aircraft at an airport can improve the airport surface operations and aircraft scheduling. The generalized dynamic programming algorithm is an exact algorithm, and it finds the optimal solution for the two runway scheduling problem. The performance of the generalized dynamic programming algorithm is assessed by comparing its running time with a published dynamic programming algorithm for the two runway scheduling problem. The results from the generalized dynamic programming algorithm show that this algorithm runs much faster than the dynamic programming algorithm. The local search heuristic with k − exchange neighborhoods has a short running time in the order of seconds, and it finds an approximate solution. The performance of this heuristic is assessed based on the quality of the solution found by the heuristic and its running time. The results show that the solution found by the heuristic for a 25 aircraft problem has an average savings of approximately 15 percent in delays with respect to a first come-first served solution. Also, the solutions produced by a 3-opt heuristic for a 25 aircraft scheduling problem has an average quality of 8 percent with respect to the optimal solution found by the generalized dynamic programming algorithm. The heuristic can be used for both real-time and fast-time simulations of airport surface operations, and it can also provide an upper limit for an exact algorithm. Aircraft arrival scheduling problems may also be addressed using the generalized dynamic programming algorithm and the local search heuristic with slight modification to the constraints.

Estimation of Distribution Algorithm (EDA) is a branch of evolutionary computation that learn a probabilistic model of good solutions. Probabilistic models are used to represent relationships between solution variables which may give useful, human-understandable insights into real-world problems. Also, developing an effective PM has been shown to significantly reduce function evaluations needed to reach good solutions. This is also useful for real-world problems because their representations are often complex needing more computation to arrive at good solutions. In particular, many real-world problems are naturally represented as permutations and have expensive evaluation functions. EDAs can, however, be computationally expensive when models are too complex. There has therefore been much recent work on developing suitable EDAs for permutation representation. EDAs can now produce state-of-the-art performance on some permutation benchmark problems. However, models are still complex and computationally expensive making them hard to apply to real-world problems. This study investigates some limitations of EDAs in solving permutation and scheduling problems. The focus of this thesis is on addressing redundancies in the Random Key representation, preserving diversity in EDA, simplifying the complexity attributed to the use of multiple local improvement procedures and transferring knowledge from solving a benchmark project scheduling problem to a similar real-world problem. In this thesis, we achieve state-of-the-art performance on the Permutation Flowshop Scheduling Problem benchmarks as well as significantly reducing both the computational effort required to build the probabilistic model and the number of function evaluations. We also achieve competitive results on project scheduling benchmarks. Methods adapted for solving a real-world project scheduling problem presents significant improvements.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Neste trabalho foram tratados dois problemas: o primeiro à denominado Continuous Permutation Flowshop Scheduling Problem (CPFSP), que possui a restriÃÃo de que nenhuma tarefa pode esperar por processamento entre mÃquinas consecutivas; o segundo à denominado de Permutation Flowshop Scheduling Problem (PFSP), em que a restriÃÃo anterior nÃo existe. A metaheurÃstica Algoritmo GenÃtico (AG) tem sido aplicada com sucesso ao PFSP, mas atà o momento nÃo foi encontrado na literatura algo que mostre que o AG à um bom mÃtodo para o CPFSP. O objetivo deste trabalho foi desenvolver um AG eficiente paras esses dois problemas, mas que nÃo precisa utilizar inicializaÃÃo eficiente e/ou hibridizaÃÃo com outra tÃcnica de busca. O desenvolvimento do AG proposto levou em consideraÃÃo as caracterÃsticas, diversificaÃÃo e a intensificaÃÃo, que inspiraram a criaÃÃo de trÃs procedimentos que melhoraram o desempenho do AG proposto. Foram realizados vÃrios experimentos com as instÃncias de Taillard (1993), Reeves (1995) e Heller (1960). Os resultados foram comparados com outros mÃtodos encontrados na literatura. Foram construÃdos polinÃmios com a utilizaÃÃo de InterpolaÃÃo Lagrangeana para determinar o tempo execuÃÃo do AG proposto. Por fim, o mÃtodo foi aplicado num problema real. Os resultados mostraram que o AG proposto à o melhor mÃtodo para o CPFSP e que fica muito prÃximo do melhor AG encontrado na literatura com inicializaÃÃo eficiente para o PFSP