A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

New heuristics for total tardiness minimization in a flexible flowshop

This paper analyses the total tardiness minimization in a flowshop with multiple processors at each stage. While there is considerable research to minimize the makespan, very little work is reported on minimizing the total tardiness for this problem. This research focuses on heuristic methods that consider this environment as a series of parallel machine problems. New dispatching rules are introduced. One of the proposed rules is able to deal with jobs that will come afterwards and not only the available jobs at the decision time. Dispatching rules are also associated with classical (forward and backward) and new list scheduling algorithms. A special scheduling algorithm able to deal with idle times is proposed. Computational experiments in a set of 4,320 literature instances show that the developed heuristics are competitive and outperforms their classical counterparts.     

The crane scheduling problem: models and solution approaches

In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.     

Maximizing business value by optimal assignment of jobs to resources in grid computing

An important problem that arises in the area of grid computing is one of optimally assigning jobs to resources to achieve a business objective. In the grid computing area, however, such scheduling has mostly been done from the perspective of maximizing the utilization of resources. As this form of computing proliferates, the business aspects will become crucial for the overall success of the technology. Hence, we discuss the grid scheduling problem from a business perspective. We show that this problem is not only strongly NP-hard, but it is also non-approximable. Therefore, we propose heuristics for different variants of the problem and show that these heuristics provide near-optimal solution for a wide variety of problem instances. We show that the execution times of proposed heuristics are very low, and hence, they are suitable for solving problems in real-time. We also present several managerial implications and compare the performance of two widely used models in the real-time scheduling of grid computing.     

An Almost Optimal Heuristic for Preemptive C max Scheduling of Dependent Tasks on Parallel Identical Machines

We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.     

Order acceptance and scheduling on two identical parallel machines

We study the order acceptance and scheduling problem on two identical parallel machines. At the beginning of the planning horizon, a firm receives a set of customer orders, each of which has a revenue value, processing time, due date, and tardiness weight. The firm needs to select orders to accept and schedule the accepted orders on two identical parallel machines so as to maximize the total profit. The problem is intractable, so we develop two heuristics and an exact algorithm based on some optimal properties and the Lagrangian relaxation technique. We evaluate the performance of the proposed solution methods via computational experiments. The computational results show that the heuristics are efficient and effective in approximately solving large-sized instances of the problem, while the exact algorithm can only solve small-sized instances.     

Beam search heuristics for quadratic earliness and tardiness scheduling

In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

Improving degree-based variable ordering heuristics for solving constraint satisfaction problems

In this paper, we improved two classical degree-based variable ordering heuristics, \(\frac{\textit{Dom}}{\textit{Ddeg}}\) and \(\frac{\textit{Dom}}{\textit{Wdeg}}\). We propose a method using the summation of constraint tightness in degree-based heuristics. We also propose two methods to calculate dynamic constraint tightness for binary extensional constraints and non-binary intensional constraints respectively. Our work shows how constraint tightness can be practically used to guide search. We performed a number of experiments on some benchmark instances. The results have shown that, the new heuristics improve the classical ones by both computational time and search tree nodes and they are more efficient than some other successful heuristics on the instances where the classical heuristics work well.     

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

Heuristics for Flowshop Scheduling Problems Minimizing Mean Tardiness

Several heuristics are presented for the flowshop scheduling problem with the objective of minimizing mean tardiness. We consider the cases in which job sequences on all machines are the same (permutation flowshop) and in which they may be different. For the former case, the various methods that have been devised for minimizing the makespan are modified for our objective, while the list scheduling algorithm is used for the latter case. These heuristics are tested and compared with each other on randomly-generated test problems.     

Some effective heuristics for no-wait flowshops with setup times to minimize total completion time

In this work, we consider a complex flowshop scheduling problem in which both no-wait and separate setup times are considered. The optimisation criterion is the minimisation of the total completion time. We propose an effective dominance rule for the four machine case that can also be used for m machines. Five simple and fast heuristics are proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). An extensive computational evaluation is carried out with two sets of 5,400 instances. All seven methods are compared to two recent algorithms. The results, confirmed by thorough statistical analyses, show that the proposed methods are more effective and efficient when compared to the best existing algorithms in the literature for the considered problem.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs

We consider the bicriteria scheduling problem of minimizing the number of tardy jobs and average flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective in the supply chain. We propose four new heuristics to solve this multiobjective scheduling problem. Two of these heuristics are constructive algorithms based on beam search methodology. The other two are metaheuristic approaches using a genetic algorithm and tabu-search. Our computational experiments indicate that the proposed beam search heuristics find efficient schedules optimally in most cases and perform better than the existing heuristics in the literature.     

A composite algorithm for multiprocessor scheduling

A composite algorithm is developed for the classical problem of scheduling independent jobs on identical parallel machines with the objective of minimizing the makespan. The algorithm at first obtains a family of initial partial solutions and combines these partial solutions until a feasible solution is generated. Then local search procedures are used for improving the solution. The effectiveness of this approach is evaluated through extensive computational comparisons with recent improvement heuristics for different classes of benchmark instances.     

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Adapting Branch-and-Bound for Real-World Scheduling Problems

Many sequencing and scheduling problems can be formulated as 0-1 integer programs and, in theory, solved using a branch-and-bound approach. In practice, real-world instances of these problems are usually solved using heuristics. In this paper we demonstrate the benefits of incorporating an intuitive, user-controlled variable-tolerance into a depth-first branch-and-bound algorithm. The tolerance comprises two components: a variable depth tolerance and a variable breadth tolerance. A sample scheduling problem is thoroughly analysed to illustrate empirically parameter impact on solution quality and execution time. Then, results based on several real-world problems are discussed.     

Roster evaluation based on classifiers for the nurse rostering problem

The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100 % correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.