A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

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.     

A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

In this paper, we address the three-machine flowshop scheduling problem. Setup times are considered separate from processing times, and the objective is to minimize total completion time. We show that the three-site distributed database scheduling problem can be modeled as a three-machine flowshop scheduling problem. A lower bound is developed and a dominance relation is established. Moreover, an upper bound is developed by using a three-phase hybrid heuristic algorithm. Furthermore, a branch-and-bound algorithm, incorporating the developed lower bound, dominance relation, and the upper bound is presented. Computational analysis on randomly generated problems is conducted to evaluate the lower and upper bounds, the dominance relation, and the branch-and-bound algorithm. The analysis shows the efficiency of the upper bound, and, hence, it can be used for larger size problems as a heuristic algorithm.     

NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time

Baker and Nuttle [K.R. Baker, H.L.W. Nuttle, Sequencing independent jobs with a single resource, Naval Research Logistics Quarterly 27 (1980) 499–510] studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true.     

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 multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem

We extend the dynasearch technique, recently proposed by Congram et al., in the context of time-dependent combinatorial optimization problems. As an application we consider a general time-dependent (idleness) version of the well known single-machine total weighted tardiness scheduling problem, in which the processing time of a job depends on its starting time of execution. We develop a multi-start local search algorithm and present experimental results on several types of instances showing the superiority of the dynasearch neighborhood over the traditional one.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

An improved branch-and-bound algorithm for the two machine total completion time flow shop problem

We consider the two machine total completion time flow shop scheduling problem. This problem is known to be NP-Hard in the strong sense. An improved Lagrangean relaxation approach is proposed. Two new dominance criteria are introduced to curtail the enumeration tree. A branch-and-bound algorithm capable of solving to optimality medium size problem instances is presented.     

Minimizing the total completion time in a single-machine scheduling problem with a learning effect

This paper introduces a new time-dependent learning effect model into a single-machine scheduling problem. The time-dependent learning effect means that the processing time of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. In most related studies, the actual job processing time is assumed to be a function of its scheduled position when the learning effect is considered in the scheduling problem. In this paper, the actual processing time of a job is assumed to be proportionate to the length and position of the already scheduled jobs. It shows that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. It also shows that the shortest processing time (SPT) rule provides the optimum sequence for the addressed problem.     

Dominance-based heuristics for one-machine total cost scheduling problems

We study the one-machine scheduling problem with release dates and we look at several objective functions including total (weighted) tardiness and total (weighted) completion time. We describe dominance rules for these criteria, as well as techniques for using these dominance rules to build heuristic solutions. We use them to improve certain well-known greedy heuristic algorithms from the literature. Finally, we introduce a Tabu Search method with a neighborhood based on our dominance rules. Experiments show the effectiveness of our techniques in obtaining very good solutions for all studied criteria.     

A matheuristic approach for the two-machine total completion time flow shop problem

This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n ²) variables and O(n) constraints.     

Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect

In this study, we introduce a time-dependent learning effect into a single-machine scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. We introduce it into a single-machine scheduling problem and we show that it remains polynomially solvable for the objective, i.e., minimizing the total completion time on a single machine. Moreover, we show that the SPT-sequence is the optimal sequence in this problem.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

A memetic algorithm for the total tardiness single machine scheduling problem

In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics.     

A class of on-line scheduling algorithms to minimize total completion time

We consider the problem of scheduling jobs on-line on a single machine and on identical machines with the objective to minimize total completion time. We assume that the jobs arrive over time. We give a general 2-competitive algorithm for the single machine problem. The algorithm is based on delaying the release time of the jobs, i.e., making the jobs artificially later available to the on-line scheduler than the actual release times. Our algorithm includes two known algorithms for this problem that apply delay of release times. The proposed algorithm is interesting since it gives the on-line scheduler a whole range of choices for the delays, each of which leading to 2-competitiveness.We also show that the algorithm is 2α competitive for the problem on identical machines where α is the performance ratio of the Shortest Remaining Processing Time first rule for the preemptive relaxation of the problem.     

The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard

Although the single machine scheduling problem to minimize the total weighted completion times with the sum-of-processing time based learning or aging effects have been known for a decade, it is still an open question whether these problems are strongly NP-hard. We resolve this issue and prove them to be strongly NP-hard with the learning effect as well as with the aging effect. Furthermore, we construct an exact parallel branch and bound algorithm for the problem with general sum-of-processing time based models, which can solve optimally moderate problem instances in reasonable time.     

Recovering Beam Search: Enhancing the Beam Search Approach for Combinatorial Optimization Problems

A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by the beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated p-median location problem. In both cases the method strongly improves the performances with respect to the basic beam search approach and is competitive with the state of the art heuristics.