Search

This paper studies the computation of ensembles of priority rules for the One Machine Scheduling Problem with variable capacity and total tardiness minimization. Concretely, we address the problem of building optimal ensembles of priority rules, starting from a pool of rules evolved by a Genetic Programming approach. Building on earlier work, we propose a number of new algorithms. These include an iterated greedy search method, a local search algorithm and a memetic algorithm. Experimental results show the potential of the proposed approaches. [ABSTRACT FROM AUTHOR]

• New priority rules to solve the (1 , Cap (t) ∥ ∑ T max) problem are evolved by a Memetic Genetic Programming (MGP) approach. • MGP exploits some neighbourhood structures designed specifically for the space of priority rules. • A compelling experimental study is performed across a new benchmark set of instances of the (1 , Cap (t) ∥ ∑ T max) problem. Priority rules combined with schedule generation schemes are a usual approach to online scheduling. These rules are commonly designed by experts on the problem domain. However, some automatic method may be better as it could capture some characteristics of the problem that are not evident to the human eye. Furthermore, automatic methods could devise priority rules adapted to particular sets of instances of the problem at hand. In this paper we propose a Memetic Algorithm, which combines a Genetic Program and a Local Search algorithm, to evolve priority rules for the problem of scheduling a set of jobs on a machine with time-varying capacity. We propose a number of neighbourhood structures that are specifically designed to this problem. These structures were analyzed theoretically and also experimentally on the version of the problem with tardiness minimization, which provided interesting insights on this problem. The results of the experimental study show that a proper selection and combination of neighbourhood structures allows the Memetic Algorithm to outperform previous approaches to the same problem. [ABSTRACT FROM AUTHOR]

On-line scheduling is often required in a number of real-life settings. This is the case of distributing charging times for a large fleet of electric vehicles arriving stochastically to a charging station working under power constraints. In this paper, we consider a scheduling problem derived from a situation of this type: one machine scheduling with variable capacity and tardiness minimization, denoted (1 , C a p (t) | | ∑ T i). The goal is to develop new priority rules to improve the results from some classical ones as Earliest Due Date (EDD) or Apparent Tardiness Cost (ATC). To this end, we developed a Genetic Programming (GP) approach. The efficiency of this algorithm relies on some smart representation of the expression trees. Besides, we restrict the search space to that of dimensionally compliant expressions, which allows GP to reach single and clear solutions. We conducted an experimental study showing that GP is able to evolve new rules that outperform ATC and EDD using the same problem attributes and operations. • Genetic Programming is used to evolve priority rules for a scheduling problem. • The evolved priority rules outperform classic rules developed manually. • Dimensionally compliant rules are compared to general rules. • Evolving ensembles of rules is an interesting approach. [ABSTRACT FROM AUTHOR]