Elsevier

Computers & Operations Research

Volume 66, February 2016, Pages 141-152
Computers & Operations Research

The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective

https://doi.org/10.1016/j.cor.2015.08.010Get rights and content

Highlights

  • A minmax regret single machine problem is considered.

  • Multiple methods to evaluate the maximum regret of a schedule are considered.

  • A new lower bound and a previously proposed dominance rule are studied.

  • A branch-and-bound algorithm is proposed for the resolution of the problem.

  • The approximation ratio of the midpoint scenario heuristic is analyzed.

Abstract

Single machine scheduling is a classical optimization problem that depicts multiple real life systems in which a single resource (the machine) represents the whole system or the bottleneck operation of the system. In this paper we consider the problem under a weighted completion time performance metric in which the processing time of the tasks to perform (the jobs) are uncertain, but can only take values from closed intervals. The objective is then to find a solution that minimizes the maximum absolute regret for any possible realization of the processing times. We present an exact branch-and-bound method to solve the problem, and conduct a computational experiment to ascertain the possibilities and limitations of the proposed method. The results show that the algorithm is able to optimally solve instances of moderate size (25–40 jobs depending on the characteristics of the instance).

Introduction

Single machine scheduling is a classical problem thoroughly studied in the literature (see [9], [12], [16], [17], [26], [33], [34] among others). The objective of the problem is to ascertain the optimal sequence in which the tasks (jobs) that define the problem need to be performed in a machine, in order to optimize some performance measure. In addition to its theoretical interest, and its use on real life situations in which only one resource (machine) exists, the problem also models situations in which the production system is taken as a whole (hence, it is considered to be a unity) or there is a bottleneck operation that dictates the performance of the production system.

While the most studied formulations correspond to deterministic problems [9], [33], [34], [17] that is, formulations in which all of the parameters are known and fixed, formulations with different characterizations of the uncertainty have also been studied [30], [35], [26], [14], [2], [5].

Among the different alternatives to model uncertainty, we highlight the use of probability distribution functions to describe processing times [35], [14], [5], the representation of possible processing times through scenarios [10], [18], and the use of intervals to define the processing time of the jobs [11], [30], [2].

In this paper we study an interval data minmax regret (IDMR) (see [11], [1], [30]) formulation of the single machine weighted sum of completion times problem (WCTP) [29], [26]. In this formulation, the uncertainty on the processing time is represented using intervals, and the aim is to find a sequence that minimizes the maximum regret for all of the possible scenarios (that is, the sequence that minimizes the maximum absolute deviation between its solution and the optimal solution for each realization of processing times). Hence, the objective reflects a robust criterion which can be associated to a risk-averse decision maker that tries to hedge against the worst-case performance. This problem is referred as the Robust Weighted Completion Time Problem (RWCTP) throughout the paper.

While the robust minmax regret sum of completion times problem has been studied in the literature (see [11], [19], [37], [20], [15]); to the best of our knowledge its weighted counterpart has not been previously considered. We conjecture that the cause for this lack of research directed toward its resolution is the inapplicability of the classical results used to evaluate a solution in multiple IDMR problems (see, e.g. [1]), which leads to an absence of a viable method to evaluate the maximum regret of a given sequence.

In this paper we deal with the previous issue and we propose two different methods to evaluate the maximum regret of any given solution: one based on enumeration, and a second based on a dynamic programming (DP) formulation [6]. Both methods build upon the identification of a subset of scenarios containing the worst case scenario. Note that this approach differs from other studied IDMR problems in which the worst case scenario and/or the worst case alternative are obtained by solving some classical optimization problem.

Then, a branch-and-bound procedure using a novel lower bound method and a previously known dominance rule [30] is used to enumerate all of the solutions. The method is initialized using a heuristic which is shown to provide a 2-approximation, and if the lower bound or the dominance rule are not able to discard a solution during enumeration, the maximum regret of the said solution is obtained using one of the methods described above.

A computational experiment using instances from previous works on other weighted completion time problems with interval data [30], [2] shows that the proposed branch-and-bound is capable of optimally solving instances with up to 25 jobs if the variability of processing times is high, and instances with up to 40 jobs if the variability is low. Furthermore, the applicability and the approximation ratio of a simple heuristic for IDMR problems, the midpoint scenario heuristic (see for example [19], [15]) is also considered.

Note that the size of these instances is smaller than the size of the instances solvable for the unweighted case, in which larger instances can be solved to optimality (see [23], [8]). Also note that the RWCTP includes an additional level of complexity, as the objective function depends not only on the absolute but also on the relative position of each pair of jobs. Nevertheless, the proposed branch-and-bound method is able to solve medium sized instances to optimality within limited running times. The results for the midpoint scenario heuristic in optimally solved instances show that it provides very reduced optimality gaps, and thus it appears as a good alternative if the solution of larger instances is required.

The rest of the paper is structured as follows. In Section 2 we describe the problem; we study the previous work on related problems and we put forward some notation used in the following sections. Section 3 is devoted to the contributions of this work and the proposed branch-and-bound algorithm. Section 4 sets forth a computational experiment to evaluate the efficacy of the algorithm proposed in Section 3. Finally, Section 5 puts forward the conclusions of this work. Two appendices are included: Appendix A is devoted to the approximation guarantees of the midpoint scenario heuristic for the RWCTP; and Appendix B, which can be found in the electronic Supplementary Material, provides additional results from the computational experiment reported in Section 4.

Section snippets

Description of the deterministic problem

The one machine scheduling problem with weighted sum of completion times (WCTP) is a classical problem, see for example Pinedo [26]. According to the notation proposed in Graham et al. [12], the problem corresponds to 1wjCj, and it can be formally described as follows: n independent jobs J={J1,J2,,Jn} have to be processed over a single machine that can handle at most one job at a time. Each job Ji, 1in, is available for processing at time zero, requires a processing time pi>0 and has a

The robust (minmax regret) weighted completion time problem with interval processing times

This section puts forward the contributions of this work. As none of the results in the literature can be used to define a method to obtain the worst-case scenario for a given sequence σ, the topic is discussed in Section 3.1. First we prove that only extreme scenarios need to be considered, and then we provide an alternative to the enumeration of all of the extreme scenarios based on the enumeration of the worst-case alternatives.

The remaining sections deal with the method to obtain a sequence

Computational experiment

The computational experiment tests (a) the applicability of the different proposed methods to evaluate the maximum regret of a solution; (b) the efficiency of the proposed branch-and-bound method under varying characteristics of the instances; (c) the quality of the proposed lower bound; (d) the performance of the midpoint scenario heuristic; and (e) the effect of the characteristics of the instances on the maximum regret. The following sections give some implementation details, see Section 4.1

Conclusions

In this paper we have studied the robust (minmax regret) total weighted completion time problem with interval processing times, we have put forward different valid methods to evaluate the maximum regret, and we have proposed a branch-and-bound method to obtain the sequence that minimizes the maximum regret. Our main recommendations and findings are the following:

  • 1.

    The difficulty of the instances depends not only on the instance size but also on the degree of uncertainty (the variability of the

Acknowledgments

The author would like to express his gratitude to the reviewers for their suggestions and opinions which have greatly improved the overall quality of the paper.

References (37)

Cited by (0)

View full text