A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

This paper deals with the one-machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. A polynomial time heuristic algorithm is proposed which applies the recently introduced Recovering Beam Search (RBS) approach. The algorithm is based on a beam search procedure with unitary beam width and includes a recovering subroutine that allows to overcome wrong decisions taken at higher levels of the beam search tree. It is shown that the total number of considered nodes is bounded by n where n is the jobsize. The proposed algorithm is able to solve in very short CPU time problems with up to 500 jobs outperforming the best state of the art heuristics.     

A simulated annealing approach for the one-machine mean tardiness scheduling problem

In this paper we propose a simulated annealing approach for solving the single machine mean tardiness scheduling problem. The results of a simulation experiment indicate that the proposed method provides much better solutions than two heuristics that gave good results in previous studies. More importantly, the solutions obtained are within less than 1% of optimal solutions.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

The one-machine just-in-time scheduling problem with preemption

This paper investigates the notion of preemption in scheduling, with earliness and tardiness penalties. Starting from the observation that the classical cost model where penalties only depend on completion times does not capture the just-in-time philosophy, we introduce a new model where the earliness costs depend on the start times of the jobs. To solve this problem, we propose an efficient representation of dominant schedules, and a polynomial algorithm to compute the best schedule for a given representation. Both a local search algorithm and a branch-and-bound procedure are then derived. Experiments finally show that the gap between our upper bound and the optimum is very small.     

Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem

This paper addresses the one-machine scheduling problem where the objective is to minimize a sum of costs such as earliness–tardiness costs. Since the sequencing problem is NP-hard, local search is very useful for finding good solutions. Unlike scheduling problems with regular cost functions, the scheduling (or timing) problem is not trivial when the sequence is fixed. Therefore, the local search approaches must deal with both job interchanges in the sequence and the timing of the sequenced jobs. We present a new approach that efficiently searches in a large neighborhood and always returns a solution for which the timing is optimal.     

One-pass batching algorithms for the one-machine problem

We study the problem of batching jobs which must be processed on a single machine. In the case the jobs are all of one type and if we want to minimize the sum of completion times, we show that the greedy algorithm solves this problem. In the case of various job types we give a heuristic which has given outstanding results on randomly generated examples.     

A tree search algorithm for the crew scheduling problem

In this paper we consider the crew scheduling program, that is the problem of assigning K crews to N tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working.A zero-one integer linear programming formulation of the problem is given, which is then relaxed in a lagrangean way to provide a lower bound which is improved by subgradient optimisation. Finally a tree search procedure incorporating this lower bound is presented to solve the problem to optimality.Computational results are given for a number of randomly generated test problems involving between 50 and 500 tasks.     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.     

A branch-and-bound algorithm for the resource-constrained project scheduling problem

We describe a time-oriented branch-and-bound algorithm for the resource-constrained project scheduling problem which explores the set of active schedules by enumerating possible activity start times. The algorithm uses constraint-propagation techniques that exploit the temporal and resource constraints of the problem in order to reduce the search space. Computational experiments with large, systematically generated benchmark test sets, ranging in size from thirty to one hundred and twenty activities per problem instance, show that the algorithm scales well and is competitive with other exact solution approaches. The computational results show that the most difficult problems occur when scarce resource supply and the structure of the resource demand cause a problem to be highly disjunctive.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

Sevast'yanov's algorithm for the flow-shop scheduling problem

We consider the flow-shop scheduling problem. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. We studied and implemented different versions of the algorithm of Sevast'yanov based on linear programming to solve this problem. Using CPLEX, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz-Enscore-Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines.     

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.     

A hybrid genetic algorithm for the job shop scheduling problem

This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.     

A heuristic algorithm for the hospital health examination scheduling problem

This study considers the problem of health examination scheduling. Depending on their gender, age, and special requirements, health examinees select one of the health examination packages offered by a health examination center. The health examination center must schedule all the examinees, working to minimize examinee/doctor waiting time and respect time and resource constraints, while also taking other limitations, such as the sequence and continuity of the examination procedures, into consideration. The Binary integer programming (BIP) model is one popular way to solve this health examination scheduling problem. However, as the number of examinees and health examination procedures increase, solving BIP models becomes more and more difficult, if not impossible. This study proposes health examination scheduling algorithm (HESA), a heuristic algorithm designed to solve the health examination scheduling problem efficiently and effectively. HESA has two primary objectives: minimizing examinee waiting time and minimizing doctor waiting time. To minimize examinee waiting time, HESA schedules the various parts of each examinee’s checkup for times when the examinee is available, taking the sequence of the examination procedures and the availability of the resources required into account. To minimize doctor waiting time, HESA focuses on doctors instead of examinees, assigning waiting examinees to a doctor as soon as one becomes available. Both complexity analysis and computational analyses have shown that HESA is very efficient in solving the health examination scheduling problem. In addition to the theoretical results, the results of HESA’s application to the concrete health examination scheduling problems of two large hospitals in Taiwan are also reported.     

A hybrid evolutionary algorithm for the job shop scheduling problem

In this paper, a hybrid metaheuristic method for the job shop scheduling problem is proposed. The optimization criterion is the minimization of makespan and the solution method consists of three components: a Differential Evolution-based algorithm to generate a population of initial solutions, a Variable Neighbourhood Search method and a Genetic Algorithm to improve the population; the latter two are interconnected. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high quality solutions in short computational times using fixed parameter settings.     

A hybrid genetic algorithm for the resource-constrained project scheduling problem

In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Constrained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour’s population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30.     

A partial dual algorithm for the capacitated warehouse location problem

The Capacitated Warehouse Location Problem (CWLP) consists of the ordinary transportation problem with the additional feature of a fixed cost associated with each supplier. A supplier can be used towards meeting the demands of the customers only if the corresponding fixed cost is incurred. The problem is to determine which suppliers to use and how the customer demands should be met, so that total cost is minimised.Most of the recently published algorithms for CWLP use branch and bound based on a Lagrangian relaxation of demand constraints. Here, a partial dual of a tight LP formulation is used in order to take advantage of the properties of transportation problems. Computational results are given which show good overall performance of the algorithm, with the size of the tree search being reduced compared with previous published results.     

A sequential dual simplex algorithm for the linear assignment problem

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n²) pivots, O(n² log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally.