On-line scheduling on a single machine: minimizing the total completion time

This note deals with the scheduling problem of minimizing the sum of job completion times in a system with n jobs and a single machine. We investigate the on-line version of the problem where every job has to be scheduled immediately and irrevocably as soon as it arrives, without any information on the later arriving jobs. We prove that for any sufficiently smooth, non-negative, non-decreasing function f(n) there exists an O(f(n))-competitive on-line algorithm for minimizing the total completion time if and only if the infinite sum converges. Received: 6 May 1997 / 3 February 1999     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups

The single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the total weighted tardiness is a challenging problem due to its complexity, and has a huge number of applications in real production environments. In this paper, we propose a memetic algorithm that combines and extends several ideas from the literature, including a crossover operator that respects both the absolute and relative position of the tasks, a replacement strategy that improves the diversity of the population, and an effective but computationally expensive neighborhood structure. We propose a new decomposition of this neighborhood that can be used by a variable neighborhood descent framework, and also some speed-up methods for evaluating the neighbors. In this way we can obtain competitive running times. We conduct an experimental study to analyze the proposed algorithm and prove that it is significantly better than the state-of-the-art in standard benchmarks.     

A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals

In this paper, we consider a single batch machine scheduling problem with incompatible job families and dynamic job arrivals. The objective is to minimize the total completion time. This problem is known to be strongly NP-hard. We present several dominance properties and two types of lower bounds, which are incorporated to construct a basic branch and bound algorithm. Furthermore, according to the characteristics of dynamic job arrivals, a decomposed branch and bound algorithm is proposed to improve the efficiency. The proposed algorithms are tested on a large set of randomly generated problem instances.     

Dual constrained single machine sequencing to minimize total weighted completion time

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the generalized isotonic regression problem; the algorithm can also be used as an O(nlogn)-time timetabling routine in earliness-tardiness scheduling. Extensive computational experiments indicate that the proposed branch-and-bound algorithm competes favorably with a dynamic programming procedure. Note to Practitioners-Real-life production systems usually involve multiple machines and resources. The configurations of such systems may be complex and subject to change over time. Therefore, model-based solution approaches, which aim to solve scheduling problems for specific configurations, will inevitably run into difficulties. By contrast, decomposition methods are much more expressive and extensible. The single-machine problem and its solution procedure studied in this paper will prove useful to a decomposition method that decomposes multiple-machine, multiple-resource scheduling problems into a number of single-machine problems. The total weighted completion time objective is relevant to production environments where inventory levels and manufacturing cycle times are key concerns. Future research can be pursued along two directions. First, it seems to be necessary to further generalize the problem to consider also negative job weights. Second, the solution procedure developed here is ready to be incorporated into a machine-oriented decomposition method such as the shifting bottleneck procedure.     

A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.     

Tabu search algorithms for minimizing total completion time on a single machine with an actual time-dependent learning effect

Natural Computing - In this paper, we investigate a single machine problem with actual time-dependent learning effect considering unequal release times, where the objective is to minimize the total...     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival

This paper addresses a scheduling problem motivated by scheduling of diffusion operations in the wafer fabrication facility. In the target problem, jobs arrive at the batch machines at different time instants, and only jobs belonging to the same family can be processed together. Parallel batch machine scheduling typically consists of three types of decisions—batch forming, machine assignment, and batch sequencing. We propose a memetic algorithm with a new genome encoding scheme to search for the optimal or near-optimal batch formation and batch sequence simultaneously. Machine assignment is resolved in the proposed decoding scheme. Crossover and mutation operators suitable for the proposed encoding scheme are also devised. Through the experiment with 4860 problem instances of various characteristics including the number of machines, the number of jobs, and so on, the proposed algorithm demonstrates its advantages over a recently proposed benchmark algorithm in terms of both solution quality and computational efficiency.     

Minimizing total completion time on a single machine with a flexible maintenance activity

A problem of jointly scheduling multiple jobs and a single maintenance activity on a single machine with the objective of minimizing total completion time is considered in this paper. It is assumed that the machine should be stopped for maintenance which takes a constant duration within a predefined period. The problem is generalized from the one with a fixed maintenance in that it relaxes the starting time of the maintenance from a fixed time point to a predefined period. Both resumable and nonresumable cases are studied. First, three properties of an optimal solution to each of the two cases are identified. Then it is shown that the proposed shortest processing time (SPT) algorithm is optimal for the resumable case. As for the nonresumable case, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, it is shown that relaxing the starting time of the maintenance cannot improve the relative error bound of the SPT algorithm. The focus of the paper is presented afterwards, which is to develop a dynamic programming algorithm and a branch-and-bound algorithm to generate an optimal solution for this case. Experimental results show that these algorithms are effective and complementary in dealing with different instances of the problem.     

Minimizing total weighted completion time with an unexpected machine unavailable interval

In the past two decades, scheduling with machine availability constraints has received considerable attention. Until recently most research has focused on the setting where all machine unavailability information is known at the beginning of the scheduling horizon. In reality, this is not practical in some cases. The machine may become unavailable to process jobs due to a machine breakdown or an occurrence of an emergent job that has to be processed immediately. In both cases, the start time of the unavailable interval is unknown beforehand, and the length of the interval may not be known until the end of the interval. In this article, we consider the situation in which the scheduler has to make scheduling decisions without any knowledge of the machine unavailable intervals. Of particular interest is the problem of minimizing total weighted completion time. When there are two or more unavailable intervals on a single machine, Fu et al. (2009) have shown that the problem is exponentially inapproximable even when jobs’ weights are equal to their processing times and one has full knowledge of unavailability. So in this paper we consider the scheduling problem on a single machine with a single unavailable period. And, we assume that every job has a weight proportional to its processing time. Based on whether the unavailable interval is due to a breakdown or an emergent job, we have the breakdown model and the emergent job model. First we show that no $\tfrac{\sqrt{5}+1}{2}$ -competitive online algorithm exists for the breakdown model, and no $\tfrac{11-\sqrt{2}}{7}$ -competitive online algorithm exists for the emergent job model. Next, we show that the simple LPT rule can give a 2- and a $\tfrac{9}{5}$ -competitive ratio for the breakdown model and the emergent job model, respectively. Further, we show that the ratios are tight by examples. For the offline case, we show that the First Fit LPT (FF-LPT) rule can give a tight approximation ratio of 2 and 4/3 for the breakdown model and the emergent job model, respectively. Finally, our experimental results show that, in practice, both LPT and FF-LPT perform very well and the performance improves when the number of jobs $n$ increases. In both models, when $n \ge 50$ , the worst case error ratio is much better than the theoretical bounds.     

An exact extended formulation for the unrelated parallel machine total weighted completion time problem

The plethora of research on \(\mathcal {NP}\)-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a non-preemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decomposition-based algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

A global constraint for total weighted completion time for unary resources

We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, we propose an O(n ⁴) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

Lower bounds for minimizing total completion time in a two-machine flow shop

For the -hard problem of scheduling n jobs in a two-machine flow shop so as to minimize the total completion time, we present two equivalent lower bounds that are computable in polynomial time. We formulate the problem by the use of positional completion time variables, which results in two integer linear programming formulations with O(n ²) variables and O(n) constraints. Solving the linear programming relaxation renders a very strong lower bound with an average relative gap of only 0.8% for instances with more than 30 jobs. We further show that relaxing the formulation in terms of positional completion times by applying Lagrangean relaxation yields the same bound, no matter which set of constraints we relax.