key: cord-0045990-7i2d8tau authors: Bożejko, Wojciech; Rajba, Paweł; Wodecki, Mieczysław title: Robust Single Machine Scheduling with Random Blocks in an Uncertain Environment date: 2020-05-25 journal: Computational Science - ICCS 2020 DOI: 10.1007/978-3-030-50436-6_39 sha: 9290ce1f9aa8e1548544e069de354297dd63b387 doc_id: 45990 cord_uid: 7i2d8tau While scheduling problems in deterministic models are quite well investigated, the same problems in an uncertain environment require very often further exploration and examination. In the paper we consider a single machine tabu search method with block approach in an uncertain environment modeled by random variables with the normal distribution. We propose a modification to the tabu search method which improves the robustness of the obtained solutions. The conducted computational experiments show that the proposed improvement results in a much more robust solutions than the ones obtained in the classic block approach. Uncertainty occurs in many production processes and has a direct impact on their smooth execution. For instance it is important in construction domain to deliver goods with no delays, but it is not easy to meet this requirement as the transportation time depends on many external factors like weather conditions, traffic jams, driver's condition and many others. Moreover, effective solving practical problems and taking the best approach requires also thorough knowledge of the process or production system and values of all parameters. For example an uncertain data of the duration of activities (operations) can be measured and in result: approximated as deterministic ones in case the variance is small enough, modeled by an appropriate probabilistic distribution or determined the membership function for the fuzzy representation. So, as in practice it is difficult to clearly determine the process parameters, quite often safe ones are taken (e.g. assume longer transportation time) what is an opportunity for further improvements. Research on scheduling problems carried out for many years is related primarily to deterministic models where the key assumption is that parameters are well defined. For those, mostly belonging to the class of strongly NP -hard problems, a number of very effective approximate algorithms have been developed. Solutions determined by these algorithms are very often only slightly worse from the optimal ones. In practice, however, as already mentioned, some parameters (e.g. operation times) may differ during the process execution from the initially assumed values. This can cause that the actual cost of execution is much bigger than expected what leads to either losing optimality or even acceptability (feasibility) of solutions. In order to close that gap in recent years more and more research has been conducted on developing methods which find more robust solution resistant to data disturbance. Uncertain parameters are usually represented by random variables or fuzzy numbers and extensive review of methods and algorithms for solving optimization problems with random parameters is presented by Vondrák in monograph [12] and newer of Shang et al. [9] , Soroush [10] , Xiaoqiang et al. [14] , Urgo and Vancza [11] , Zhang et al. [15] and Bożejko et al. [2] , [4] and [6] . In this paper we consider a single machine scheduling problem with due dates in two variants where either job execution times or due dates are represented by independent variables with normal distribution. We also present some properties of the problem (so-called block elimination properties) accelerating the review of neighborhoods in local search algorithms. The main goal is to compare the robustness of the block-based tabu search algorithm in the classic and the proposed random model and show the superiority of the latter one. Let J = {1, 2, . . . , n} be a set of jobs to be executed on a single machine. At any given moment a machine can execute exactly one job and all jobs must be executed without preemption. For each task i ∈ J let p i be a processing time, d i be a due date and w i be a cost for tardy jobs. Every sequence of jobs execution can be presented as a permutation π = (π(1), π(2), . . . , π(n)) of items from the set J . Let Π be the set of all permutations of the set J . For every permutation π ∈ Π we define as a completion time of a job π(i). The cost of jobs' execution determined by the permutation π is as follows where We consider the optimization problem where the goal is to find a permutation π * ∈ Π which minimizes the cost of jobs' execution: In order to simplify the further considerations we assume w.l.o.g. that at any moment the considered solution is the natural permutation, i.e. π = (1, 2, . . . , n). Moreover, if X is a random variable, then F X denotes its cumulative distribution function. In this section we consider a TWT problem with uncertain parameters. We investigate two variants: (a) uncertain processing times and (b) uncertain due dates. Random processing times are represented by random variables with the normal distributionp i ∼ N (p i , c · p i )), i ∈ J . Other parameters, i.e. due dates d i and costs w i are deterministic. Then completion timesC i are random variables: and delays are random variables For each permutation π ∈ Π the cost in the deterministic model is defined as (1)). A corresponding cost in the random model is defined as the following random variable: In order to compare the costs of permutations from the set Π we introduce the following comparison function to calculate the value: where E(Ũ i ) is the expected value of the random variableŨ i . Random due dates are represented by random variables with the normal distri- Other parameters, i.e. processing times p i and costs w i are deterministic. Delay indication is a random variablẽ In this variant of the problem we apply the comparison function (5) defined in the previous section. The TWT problem in both variants (i.e. with random processing times and random due dates) is to find a permutation for which the comparison function (5) is minimal in the set Π. We denote the probabilistic version of the problem as TWTP. As the deterministic version, the problem belongs to the class of NP -hard problems. Each permutation π ∈ Π is decomposed into m (m n) subpermutations B 1 , . . . , B m , called random blocks for π, which satisfy the following criteria: 2. All jobs j ∈ B k satisfy either the condition or the condition 3. B k is maximal subsequence of π where all the jobs satisfy either (7) or (8). We distinguish two types of blocks: -E-Random Blocks, denoted as B E k , the ones satisfying condition (7), -T-Random Blocks, denoted as B T k , the ones satisfying condition (8). . . , l k ) and C = (l k + 1, . . . , n). Estimated value of comparison function can be calculated as follows: Proof. Let's consider the following 2 cases. A. B is random E-block. Then we have: Applying our assumption that B fulfills (7) (i.e. B is a random E-block) as well as by definition ofC i and the problem formulation where every realization ofC i will be less or equal than realization of C l k we obtain that Having that we can proceed as follows: what leads us to the conclusion that for each permutation B ∈ B we have B. B is random T -block. Then we have: By definition of S s k andC i (i ∈ B) we can easily observe the following: Having that and applying our assumption that B fulfills (8) what leads us to the conclusion that for each permutation B ∈ B we have That concludes the proof. The above theorem also holds in case where we consider only random processing times or only random due dates and each case the proof is analogous. It is easy to show the following. For the variant with random processing times p i we have: and for the variant with random due datesd i we have: Combining the above with assumptions expressed in (7) and (8) and adapted to respective variants, we apply the following rules to modify the base tabu search method. For the variant with random processing timesp i : For the variant with random due datesd i : In this section we present the results of the robustness property comparison between the tabu search method with blocks and the tabu search method with blocks and theorem applied in a way described in Sect. 4. All tests are executed with a modified version of tabu search method described in [1] . The algorithm has been configured with the following parameters: π = (1, 2, . . . , n) is an initial permutation, n is the length of tabu list and n is the number of algorithm iterations where n is the tasks number. Both methods have been tested on instances from OR-Library ( [8] ) where there are 125 examples for n = 40, 50 and 100 (in total 375 examples). For each example and each parameter c = 0.02, 0.04, 0.06 and 0.08 (expressing 4 levels of data disturbance) 100 randomly disturbed instances were generated according to the normal distribution defined in Sect. 3.1 (in total 400 disturbed instances per example). The full description of the method for disturbed data generation can be found in [5] . All the presented results in this section are calculated as the relative coefficient according to the following formula: which expresses by what percentage the investigated solution W is worse than the reference (best known) solution W * . Details of calculating robustness of the investigated methods can also be found in [5] . An algorithm without applied theorem we denote by AD and the one with applied theorem by AP. In Tables 1 and 2 we present a complete summary of the computational experiments results. Values from columns AD and AP in both tables represent a relative distance between solutions established by a respective algorithm and the best known solution. The distance is based on (9) and it is an average of all solutions calculated for the disturbed data on a respective disturbance level expressed by the parameter c. Value from column IF (what stands for improvement factor ) expresses the relative distance (also based on (9)) between the results obtained by AD and the results obtained by AP. We can easily observe that applying the theorem into the method improves results very significantly for all the investigated cases. We can also observe that robustness coefficients for random d i are generally worse than ones for random p i what can be explained by the fact that for random d i there are more fluctuations in disturbed data than for random p i what is implied by the disturbed data generation method. The other observation is related to the results on different disturbance levels (parameter c). With the bigger value of c we might expect the worse robustness coefficient. Surprisingly, we can observe a difference between results for random p i and random d i . For random p i the rule generally works both for AD and AP, only for AP there is a swap between c = 0.02 and c = 0.04 for N = 40 and a swap between c = 0.04 and c = 0.06 for N = 50, nevertheless those values are all very close to each other, so those swaps are actually meaningless. For d i the situation is different. The rule still works for AP, but for AD we are not able to observe any trend. That can be considered as an advantage of AP as it behaves in a more predictive and stable way than AD does. It is also worth noting the difference of trends for random p i and random d i of the comparison between AD and AP (column IF ) on different disturbance levels which are visualized on Figs. 1 and 2. While for random p i we can see that with the increase of the parameter c the gap between AD and AP is also increasing, for random d i we can observe exactly the opposite. On the other hand the order of magnitude of improvement factor (IF ) is the same for both random p i and random d i what shows that the level of improvement introduced by the presented Theorem works similarly in both considered scenarios. The tabu search method is well paralleling. According to the classification proposed by Voß [13] , four models of the parallel tabu search method can be consid- [7] . In the version proposed in this paper where block approach is applied it is natural to use MSSS or MSMS diversification strategies, because the block mechanism is quite easily parallelized (each block can be considered separately [3] ). The use of 'tree' strategies using the same start solution is also possible provided the fact that the process of searching the solution space at a later stage is diversified (e.g. by using different tabu length for individual threads or through a mechanism of dynamic tabu list length change [1] ). In the paper we considered a single machine tabu search method with block approach in an uncertain environment modeled by random variables with the normal distribution. We proposed a theorem which allows to modify the base tabu search method in a way which improves the robustness of calculated solutions. Computational experiments conducted on disturbed data confirmed substantial predominant of the method after applying the proposed theorem. Block approach-tabu search algorithm for single machine total weighted tardiness problem Stable scheduling with random processing times Parallel metaheuristics for the cyclic flow shop scheduling problem Stable scheduling of single machine with probabilistic parameters Robustness of the uncertain single machine total weighted tardiness problem with elimination criteria applied Flowshop scheduling of construction processes with uncertain parameters Computer architecture: Pipelined and parallel processor design Distributionally robust optimization for planning and scheduling under uncertainty Scheduling stochastic jobs on a single machine to minimize weighted number of tardy jobs A branch-and-bound approach for the single machine maximum lateness stochastic scheduling problem to minimize the value-at-risk Probabilistic methods in combinatorial and stochastic optimization (Doctoral dissertation Tabu search: Applications and prospects Stochastic single-machine scheduling with random resource arrival times Acknowledgments. This work was partially funded by the National Science Centre of Poland, grant OPUS no. 2017/25/B/ST7/02181 and a statutory subsidy 049U/0032/19.