The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective
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 , and it can be formally described as follows: n independent jobs have to be processed over a single machine that can handle at most one job at a time. Each job Ji, , is available for processing at time zero, requires a processing time 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)
- et al.
Minmax and minmax regret versions of combinatorial optimization problemsa survey
Eur J Oper Res
(2009) - et al.
Single machine scheduling problem with interval processing times to minimize mean weighted completion time
Comput Oper Res
(2014) Minmax regret solutions for minimax optimization problems with uncertainty
Oper Res Lett
(2000)The minmax regret permutation flow-shop problem with two jobs
Eur J Oper Res
(2006)Minimizing earliness and tardiness costs in stochastic scheduling
Eur J Oper Res
(2014)A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
Oper Res Lett
(2010)- et al.
Optimization and approximation in deterministic sequencing and schedulinga survey
Ann Discrete Math.
(1979) - et al.
Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times
Comput Oper Res
(2013) - et al.
A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion
Oper Res Lett
(2008) - et al.
Mixed integer programming formulations for single machine scheduling problems
Comput Ind Eng
(2009)