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)
A mixed integer programming approach for the single machine problem with unequal release dates
Comput Oper Res
Complexity of minimizing the total flow time with interval data and minmax regret criterion
Discrete Appl Math
Robust scheduling on a single machine to minimize total flow time
Comput Oper Res
Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times
Appl Soft Comput
Exact and heuristic algorithms for the interval data robust assignment problem
Comput Oper Res
Minimizing total weighted flow time under uncertainty using dominance and a stability box
Comput Oper Res
Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem
Comput Oper Res
Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties
Comput Oper Res
Cited by (40)
Robust job-sequencing with an uncertain flexible maintenance activity
2023, Computers and Industrial EngineeringRobust permutation flow shop total weighted completion time problem: Solution and application to the oil and gas industry
2023, Computers and Operations ResearchCitation Excerpt :To our knowledge, considering robust scheduling with weighted and unweighted versions of the total completion time objective, works about the robust flow shop are nonexistent, and only the single-machine scheduling problem (SMSP) has been addressed. Based on the minimax regret criterion, 2-approximation (Kasperski and Zieliński, 2008), heuristics (Daniels and Kouvelis, 1995) and branch-and-bound (Daniels and Kouvelis, 1995; Pereira, 2016) algorithms were proposed for the single-machine robust scheduling problem, while heuristics (Yang and Yu, 2002; Allahverdi et al., 2014), stability analysis methods (Sotskov et al., 2011; Lai et al., 2018), dynamic programming (Yang and Yu, 2002) and branch-and-cut (de Farias et al., 2010) were developed for the SMSP/minimax optimization criterion. Finally, simple iterative improvement (SII) and simulated annealing (SA) heuristics (Lu et al., 2014), along with MILP models (Lu et al., 2014; Tadayon and Smith, 2015) were developed for the SMSP with minimax budgeted uncertainty.
Robust (min–max regret) single machine scheduling with interval processing times and total tardiness criterion
2020, Computers and Industrial EngineeringCitation Excerpt :The min–max regret criterion (robust deviation) minimizes the maximum regret and is suitable in situations where the decision-maker may feel regret if he/she makes a wrong decision. The existing RO literature considers single machine scheduling problems (SMSPs) with uncertain parameters for minimizing various objective functions, such as total (weighted) completion (flow) time (Kasperski & ZielińSki, 2008; Lebedev & Averbakh, 2006; Lu et al., 2012; Pereira, 2016; Sotskov et al., 2009; Wang et al., 2020), maximum waiting time (Yang & Yu, 2002), makespan (Lu et al., 2014), maximum lateness (Kasperski, 2005), and (weighted) number of late jobs (Drwal, 2018; Drwal & Józefczyk, 2020). However, the total tardiness criterion has not received enough research attention.
The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times
2020, Computers and Operations ResearchCitation Excerpt :The distributionally robust optimization framework injects the risk-averseness of the decision maker against distributional modeling errors, due to a partial knowledge of distributional information, into the robust paradigm. Contrary to the robust optimization approach, where random data are either represented by continuous intervals (Pereira, 2016; Xu et al., 2013; Yue et al., 2018), or by a finite set of different values (also called scenarios Bertsimas et al., 2011), the uncertainty is represented through an ambiguity set, that is, a family of probability distributions that is consistent with the available raw data or experts judgements. Thanks to this paradigm, the problem can be converted into a deterministic equivalent model, which can be solved exactly quite efficiently for small instances.
Maximum excess dominance: Identifying impractical solutions in linear problems with interval coefficients
2020, European Journal of Operational ResearchCitation Excerpt :For example, the shortest path problem with interval arc cost was considered in Averbakh and Lebedev (2004). Interval representation has been used to model uncertainty in many practical problems, such as machine scheduling, inventory optimization, communication routing, transportation and resource planning (for example, see Boloukat and Foroud (2016); Chen, Hu, and Hu (2009); Pereira (2016); Schang, Hynninen, Morton, and Salo (2016); Xu and Albin (2003) and Conde, Leal, and Puerto (2018)). Many researchers have also studied optimization problems with interval coefficients (for example, see Gilbert and Spanjaard (2017); Inuiguchi and Sakawa (1995); Ishibuchi and Tanaka (1990); Oliveira and Antunes (2007); Steuer (1981)).
Risk level-driven bi-objective stochastic parallel machine scheduling problem
2019, IFAC-PapersOnLine