Microsoft Word - 1184 Article Text, Copyedited.doc Adv Syst Sci Appl 2021; 04; 115-129 Published online at https://ijassa.ipu.ru. Original Russian Text © D.A. Novikov, 2021, published in Upravlenie bolshimi sistemami / Large-Scale Systems Control, 2021, Vol. 94, pp. 5–32. Optimal Schedule to Test Independent Hypotheses Dmitry Novikov* V. A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia E-mail: novikov@ipu.ru Tel.: +74953347569 Abstract: The first stage of any creative activity consists in generating a set of hypotheses and testing them. Generally, the time, required for testing a hypothesis is random and depends on its complexity (the prior probability of testing per unit time) and on acquired experience, determined by the set of hypotheses, successfully tested before. The problem is to choose an optimal schedule of testing, i.e. minimizing the sum of expected testing times, which are essentially nonlinear past-sequence-dependent and take into account learning and deterioration effects. For this aim, the general model of creative activity is formulated and the corresponding problem of optimal scheduling is stated; the classification of subproblems is introduced. Analysis of related works demonstrates the absence of methods to find computationally “simple” solution of the problem in hand. The used method of analytical proof of certain monotonic schedule optimality consists in reordering of two adjacent hypothesis, violating monotonicity. Main result is a set (for different subproblems) of sufficient conditions, under which the monotonic “simple-to-complex” schedule is optimal: the hypotheses are arranged in ascending order of their complexity. Keywords: schedule theory, past-sequence-dependent scheduling problem, time-dependent processing times, learning and deterioration effects, creative activity, hypotheses testing 1. INTRODUCTION In the Introduction the structure of creative activity is analyzed (subsection 1.1), then a model of the first phase of creative activity is formulated (subsection 1.2) and the problem of optimal scheduling is stated (subsection 1.3). Parallelly the motivation is exposed, as well as the main known results (related works) are discussed. 1.1. Structure of Creative Activity Activity is a dynamic interaction of a human with the reality in which this human represents a subject (actor) purposefully influencing an object (subject matter) [0]. Activity is a form of human actions aimed at cognizing and transforming the surrounding world, humans themselves, and the conditions of their existence. Creative activity is an activity that produces an a priori uncertain demand for the results of an a priori unknown activity with a technology created during the new activity. Three phases of the life cycle of creative activity (subject matter) were identified in the paper [2]: 1) the discovery of a new subject matter and the accumulation of basic knowledge (the generation of hypotheses and their testing); 2) mastering the subject matter; * Corresponding author: novikov@ipu.ru 116 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) 3) mass productive use. As was shown therein, creativity is concentrated in goal-setting. For scientific or art activities, it is concentrated in the generation and testing of hypotheses [3, 4]. A reasonable approach to the second phase involves the mathematical models of experience [5]. The third phase can be described using structural and algorithmic models [0] and optimization models [6]. For reflecting the first phase, mathematical models for choosing an optimal schedule to test hypotheses will be suggested below. 1.2. A Model of the First Phase of Creative Activity Consider a subject mastering K types of activity: a subject acquires K knowledge elements or tests K hypotheses on a single subject matter, choosing an appropriate schedule to do it himself. Let any schedule be admissible. Having chosen a schedule, the subject begins to test the hypotheses one by one (for the sake of convenience, in ascending order of their numbers.) The hypothesis testing process is not interrupted and runs as follows. By the end of a next discrete-time instant (step), the hypothesis can either have been already tested or not. The process continues until the hypothesis is tested. Hypothesis k is characterized by the initial level of mastering (“initial knowledge”) and the prior probability of testing per unit time (one step) This probability conditionally characterizes the complexity of testing. (For example, the complexity of testing can be inversely proportional to the probability of testing and vice versa.) Assume that testing of hypothesis k begins at step 0. According to [5], the learning level of hypothesis k (the probability that this hypothesis is tested) has the following form: , . (1) The learning level can be described either by the expected test time of hypothesis k (see below) or the time Tk(ε, L(0), wk) when the probability that hypothesis k is still untested will not exceed ε > 0: , . (2) Clearly, is a strictly monotonically decreasing and concave function of and a strictly monotonically decreasing and convex function of wk. We denote by the initial knowledge vector and by the vector of the prior probabilities of testing. Consider the strictly sequential testing of hypotheses: testing of a next hypothesis begins immediately after the completed testing of the previous one. Regardless of the schedule of testing, the total time to master the subject matter sequentially is given by Tseq(L(0), w, ε) = . (3) The aggregate learning level has the following form: , (4) where , (see (2)), and . Let the initial values of all learning levels be 0. Under this assumption, we compare the time (3) with the time of mastering the subject matter by randomly choosing the hypothesis tested at each step; for details, see the models of mastering experience in [5]. In this case, the learning level takes the form (0)kL (0,1).kw Î ( )( )1 1 (0) 1( ) t k k kLt wL = - - - 1k ,K= ( ) ( ) ln( ) ln ( , (0), 0 ) ) l 1 n ( 1 k k k k kT L L w w e e - = - - 1k ,K= ( , (0), )k k kT L we (0)kL 1(0) = ( (0),..., (0))KL LL 1( ,..., )Kw w=w ( ) ( )1 0l 1 ( )n( ) l ln 1 n k k K k L w e = - - - å 0 1 1 1 min{1 ; (1 (1 }( ) ) ( ) (1 ) )seq K t k k k L w I t Tt K e e - = = - - - ³ - å 0 k j j k T T < =å ( ) ( ) ln( ) ln 1 (0) ln 1 j j j L T w e - - = - , 1,j k K= OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 117 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) . (5) As is known [5], under the same prior probabilities of testing and arbitrary distributions p = , the expected learning level (5) achieves maximum for the uniform distribution. Therefore, assume that the “uniform random” testing strategy is used, and the prior probabilities of testing are the same and equal to w. Then , and the time when the probability that hypothesis k is still untested will not exceed ε > 0 is . Under the assumptions introduced above, the sequential test time (3) of all hypotheses is . Obviously, : the sequential testing strategy faster covers the subject matter than the uniform random testing strategy. 1.3. An Optimal Schedule to Test Independent Hypotheses: Problem Statement and Known Results We formulate the problem of an optimal schedule to test hypotheses. Let the subject tests the hypotheses in ascending order of their numbers: from 1 to K. For each hypothesis , we define the set of its “predecessors” and the function of sets , where is a continuous function. Suppose that the probability of testing depends on the complexity of the hypotheses already tested by the subject. Two cases will be considered below: the multiplicative and additive dependencies on the sum of the prior probabilities of testing for the already tested hypotheses. The problem is to find an appropriate schedule to test all hypotheses in the minimum total time. This problem belongs to the class of scheduling theory problems [7, 8] with a single machine, several jobs/tasks, and the deterioration and learning effects: the time to execute a job or set up the machine depends on the previous trajectory (history). In scheduling problems, such setup times are called past-sequence-dependent (p-s-d) or generally time- dependent [9]. The papers [10, 11] considered models with the deterioration effect (in terms of this work, the negative effect of the history, see Figure 1) in which the job execution time increases linearly with the time of beginning. Sufficient conditions were established under which an optimal schedule (by some criterion, e.g., the minimum time for completing all jobs, the minimum weighted delays, etc.) arranges the jobs in descending or ascending order of their characteristics (the minimum initial execution times, the linear dependence coefficients, etc.). In addition to linear constraints, scheduling theory deals with other, quite specific (!) constraints and dependencies (power [12], exponential [13, 14]). We will also consider a particular case of the multiplicative (7), (13) or additive (10), (14) effect of the history on the test times of hypotheses. The publications [15, 16, 17] were first to consider the learning effect in scheduling theory (in terms of this work, the positive effect of the history, see Figure 1). Within the models suggested therein, the job execution time decreases linearly with the number of preceding jobs. As was shown, the corresponding problem is generally an NP-complete problem. Particular polynomially solvable cases were presented. A V-shaped schedule turns out to be optimal in several models: the jobs are arranged first in descending order and then in the ( ) 1 ) 1 1( K t k k k k rndL p wt p = = - -å { 1 }kp , k ,K= 1 11) 1( tK k k rnd wL t K K= æ ö= - -ç ÷ è ø å ln( ) ln 1 rndT w K e = æ ö-ç ÷ è ø ( ) ln( ) ln 1seq KT w e = - seq rndT T£ 1k ,K= {1,..., 1}kN k= - 1 1 ( ) ( ) k k k k j j N wµ y - = = å 1 1: (0 ]k k , w y + ® 118 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) ascending one [18]. Clearly, monotonic schedules are special cases of V-shaped ones [19]. The model [20] includes both effects (deterioration and learning) simultaneously. Some papers consider more complicated setup, but under certain assumptions: coupled tasks [21, 22], scenario-dependent processing times [23], a set of linearly [24] or quadratic deteriorating jobs, position-and-resource-dependent processing times [25], etc. A more general approach is treating the problem of an optimal schedule to test hypotheses as a complex modification of the traveling salesman problem. The traveling salesman problem [26] with complex precedence constraints and the dependence of times on the sequence of the graph vertices and other graph properties is called the megalopolis visit problem. For this problem, dynamic programming-based solution schemes are constructed and tested in computational experiments [27]. Megalopolis visit problems are more general than scheduling problems with deterioration and learning. But as the latter, they don’t give analytical solution to the problem of optimal hypotheses testing schedule even for the simplest cases. The rest content of the paper is organized as follows. Brief Section 2 introduces a classification of the problems of an optimal schedule to test hypotheses. The main results are presented in Section 3 - sufficient conditions are established under which the monotonic “simple-to-complex” schedule is optimal. The Discussion section contains some possible prospects for applying discrete optimization methods to creative activity modeling. 2. PROBLEMS OF AN OPTIMAL SCHEDULE TO TEST HYPOTHESES: A CLASSIFICATION We return to the problem of an optimal schedule to test hypotheses. Let us introduce a binary classification system for particular cases of this problem (Figure 1). Sixteen options are possible: - The set of already tested hypotheses affects the initial level of mastering or the probability of testing for a current hypothesis. - This effect is positive, increasing the initial level of mastering or the probability of testing (the subject gains experience), or negative, decreasing the characteristics mentioned (the subject “gets tired” or overloads own cognitive capabilities). - The dependence is multiplicative or additive (see the discussion above). - The optimality criterion is the expected test time t* of a hypothesis or the time tε when the probability that the hypothesis is still untested will not exceed a given threshold ε. OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 119 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Fig. 1. Problems of an optimal schedule to test hypotheses: a binary classification Figure 1 shows the numbers of the propositions below corresponding to different particular cases (the corresponding rectangles are shaded). Note that Propositions 1–6 are proved using the same logic. Each of these propositions claims that under certain assumptions, the optimal schedule is a monotonic sequence of the hypotheses by the prior probabilities of testing (from the largest to smallest probability, or vice versa). The proof considers an arbitrary schedule of hypotheses under the assumption that a pair of “adjacent” hypotheses breaks the monotonicity. Then the test times in the original and reverse schedule are compared; it is shown that interchanging these two hypotheses will reduce the total test time of the pair. Since the test times of the hypotheses with lower numbers do not change, like the initial conditions to test the hypotheses with higher numbers, the interchange will reduce the total test time of all hypotheses. This fact proves the optimality of their corresponding monotonic schedule. The main results are presented in the next section. 3. MAIN RESULTS: OPTIMAL SCHEDULES In the multiplicative case, the learning level (unlike (1)) depends on the schedule of testing as follows: , . (6) Then Ts(L(0), w, ε) = . (7) The corresponding optimization problem is to minimize the time (7) of mastering the subject matter by choosing an appropriate schedule to test the hypotheses. Generally speaking, this is ( )( )1 1 (0) (( ) 1 ) tk k kk kt L wL Nµ= - - - 1k ,K= ( ) ( )1 ln( ) ln 1 (0) ln 1 ( ) K k k k k k L w N e µ= - - -å 120 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) a combinatorial problem: there exist K! admissible schedules. Fortunately, within definite assumptions, a simple analytical solution can be found in some cases. Let . We introduce the following assumption. A.1. The initial values of all learning levels are the same: . For all hypotheses, the previous experience has the same effect on the probabilities of testing, described by = , , where is a smooth and strictly monotonically increasing function. Consider two auxiliary lemmas. Lemma 1: If is a continuous, strictly monotonically increasing and concave function, then for any positive numbers x, y, and z such that y < z, we have . Lemma 2: If is a smooth, strictly monotonically increasing and convex function, then: a) For any positive numbers x, y, and z such that q(x) < y < z, we have . b) For any positive numbers x, y, and z such that y < z < q(x), we have , where q(x) is the solution of the differential equation . (8) The proofs of all statements are given in the Appendix. The assertions of Lemma 2 are immediate from the properties of smooth and convex functions. Proposition 1: Under Assumption A.1, let be a smooth, strictly monotonically increasing and convex function, and let j be the number of a hypothesis such that . Then interchanging hypotheses j and j + 1 will reduce the total time (7) of mastering the subject matter sequentially. Quite expectedly, Lemma 1 can be used to establish a result similar to Proposition 1 for concave monotonic functions . Now consider the additive case in which the learning level (unlike (1)) depends on the schedule of testing as follows: , . (9) Then Ts(L(0), w, ε) = . (10) 1 1 j j l l wh - = =å 0(0) 1jL L e= < - ( )jy × ( )y × 1j ,K= 1 1: (0, min ] k kw y + ® 1 1:y + + ®Â ( ) ( )x z x y z y y y+ + < 1 1:y + + ®Â ( ) ( )x z x y z y y y+ + > ( ) ( )x z x y z y y y+ + < ( ) ( ) x q x q d s q ds y y + + = ( )y × 1( )j j jq w wh +< < ( )y × ( )( )1 1 (0) (( ) 1 ) tkk k k kL t L w Nµ= - - - - 1k ,K= ( ) ( )1 ln( ) ln 1 (0) ln 1 ( ) K k k k k k L w N e µ= - - - -å OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 121 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) We introduce another assumption. A.2. The initial values of all learning levels are the same: , where L0 can be interpreted as a characteristic of the subject matter. For all hypotheses, the previous experience has the same effect on the probabilities of testing, described by = , , where is a continuous and strictly monotonically increasing function satisfying (11) for any positive numbers x, y, and z such that y < z. Some examples of the functions obeying Assumption А.2 are: - the linear function ; - the quadratic function ; - any strictly monotonically increasing and strictly convex function such that the derivative . Proposition 2: Under Assumption A.2, let j be the number of a hypothesis such that . Then interchanging hypotheses j and j + 1 will reduce the total time (10) of mastering the subject matter sequentially. Corollary 1: Consider the model (9), (10) of mastering the subject matter sequentially under Assumption A.2. In terms of the minimum total time of mastering, the optimal schedule arranges the hypotheses in descending order of the prior probabilities of testing (in ascending order of their “complexities”). In the models described above, an optimality criterion is the time to reach the learning level 1 – ε. An alternative approach involves the expected test time of hypothesis k: τk(Lk(0), wk) = (1 – Lk(0)) / wk, . (12) Clearly, τk(Lk(0), wk) is a linear decreasing function of and a strictly monotonically decreasing and convex function of wk. In the multiplicative case, the total expected time of mastering the subject matter sequentially is given by τseq(L(0), w) = . (13) We introduce another assumption similar to Assumption A.1: А.3. For all hypotheses, the previous experience has the same effect on the probabilities of testing, described by = , , where is a smooth and strictly monotonically increasing function. The following analog of Propositions 1 and 2 holds. 0(0) 1jL L e= < - ( )jy × ( )y × 1j ,K= 1: [0 1 min ]kk , wy + ® - ( ) ( )x z x y z yy y+ - + ³ - ( ) (0,1]ss ,y a a = Î 2( )s sy = ( )y × min ( ) ( )| 1 kk y w d y y dy y y = > 1j jw w +< 1k ,K= (0)kL 1 1 (0) ( ) K k k k k k L w Nµ= -å ( )jy × ( )y × 1j ,K= 1 1: (0, min ] k kw y + ® 122 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Proposition 3: Under Assumption A.3, let j be the number of a hypothesis such that and . Then interchanging hypotheses j and j + 1 will reduce the total time (13) of mastering the subject matter sequentially. Corollary 2: Consider the model (6), (13) of mastering the subject matter sequentially under Assumption A.3. In terms of the minimum total time of mastering, the optimal schedule arranges the hypotheses in descending order of the prior probabilities of testing (in ascending order of their “complexities”) if it coincides with the ordering of the prior probabilities of testing normalized by 1 minus the initial learning level. In the additive case, the total expected time of mastering the subject matter sequentially is given by τseq(L(0), w) = . (14) The following analog of Proposition 3 holds. Proposition 4: Under Assumption A.2, let j be the number of a hypothesis such that . Then interchanging hypotheses j and j + 1 will reduce the total time (14) of mastering the subject matter sequentially. Corollary 3: Consider the model (6), (14) of mastering the subject matter sequentially under Assumption A.2. In terms of the minimum total time of mastering, the optimal schedule arranges the hypotheses in descending order of the prior probabilities of testing (in ascending order of their “complexities”). Now we study the case of a continuous and strictly monotonically decreasing function . The following counterpart of Proposition 4 holds. Proposition 5: Let the initial values of all learning levels be the same: . For all hypotheses, let the previous experience have the same effect on the probabilities of testing, described by = , , where is a continuous and strictly monotonically decreasing function. Also, let j be the number of a hypothesis such that . Then interchanging hypotheses j and j + 1 will reduce the total time (13) of mastering the subject matter sequentially. Corollary 4: Consider the multiplicative case with a continuous and strictly monotonically decreasing function . In terms of the minimum total time of mastering the subject matter sequentially, the optimal schedule arranges the hypotheses in ascending order of the prior probabilities of testing (in descending order of their “complexities”). We finally examine the case in which the initial learning level depends on the schedule to test the hypotheses: 1 11 (0) 1 (0) j j j j w w L L + + < - - 1j jw w +< 1 1 (0) ( ) K k k k k k L w Nµ= - +å 1j jw w +< ( )y × 0(0)jL L= ( )jy × ( )y × 1j ,K= 1: (0,1 min ]kk wy + ® - 1j jw w +> ( )y × OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 123 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) τk( , wk) = (1 – ) / wk, , (15) where is a continuous and strictly monotonically increasing function. The total expected time of mastering the subject matter sequentially is given by τseq(w) = . (16) We introduce the following assumption. А.4. For all hypotheses, let the previous experience have the same effect on the initial value of the learning level, described by = , , where is a continuous and strictly monotonically increasing function. In the case under consideration, the following analog of Propositions 1–4 holds. Proposition 6: Under Assumption A.4, let j be the number of a hypothesis such that . Then interchanging hypotheses j and j + 1 will reduce the total time (16) of mastering the subject matter sequentially. Corollary 5: Consider the model (6), (15) of mastering the subject matter sequentially under Assumption A.4. In terms of the minimum total time of mastering, the optimal schedule arranges the hypotheses in descending order of the prior probabilities of testing (in ascending order of their “complexities”). 4. CONCLUSION: DISCRETE OPTIMIZATION PROBLEMS IN CREATIVE ACTIVITY MODELING Thus, in terms of the expected total time to test the independent hypotheses or the total time to reach a given learning level, the optimal schedule in several cases is a simple rule: the hypotheses are arranged in descending order of the prior probabilities of testing (the monotonic “simple-to-complex” schedule). Now we present general sufficient conditions for the optimality of the “simple-to-complex” schedule. Let be the test time of hypothesis , where the function is continuous and decreasing in both variables, and for any x, y, and z such that t(x, y) + t(x + y, z) > t(x, z) + t(x + z, y). As is easily checked in the case , interchanging hypotheses j and j + 1 will reduce the total time of their testing. Attempts to weaken these sufficient conditions and give them in a practically interpretable form seem a promising line of further research. Another area of interest is studying optimal schedules to test interdependent hypotheses. Graph theory and discrete optimization offer a rich apparatus to formulate and solve optimization problems for hypothesis testing and creative activity modeling. Here are some illustrative examples. Let the subject area be described by a graph containing K vertices. Graph vertices correspond to hypotheses to be tested. Hypothesis k is characterized by a pair of nonnegative numbers (ck, dk): the first number reflects the cost to test it, whereas the second one reflects its contribution to the experience of mastering the subject area. Assume that the experience is additive: under the sequential testing of all hypotheses in ascending order of their numbers, ( )kz h ( )kz h 1k ,K= 1: [0,1)z + ® 1 1 ( )K k k kw z h = -å ( )jz × ( )z × 1j ,K= 1: [0 1),z + ® 1j jw w +< ( )k k kt t ,wh= 1k ,K= ( , )t × × 1j jw w +< 124 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) when the subject starts testing hypothesis k, the experience is , and the total cost of the already tested hypotheses is . We define the complexity of each hypothesis as . (The complexity depends on the schedule to test all hypotheses.) Note that with such a definition, the complexity can be negative. We define the complexity of each schedule to test all hypotheses (each Hamilton circuit ρ = (i1, i2, …, ik, …, iK) in the graph) as the maximum value among the complexities to test different hypotheses in this schedule: . The problem is to find a schedule to test all hypotheses (a Hamilton circuit) of minimum complexity: . Under the assumptions introduced above, this combinatorial problem has a simple analytical solution (see general results in [0]): – Take the hypotheses satisfying , arrange them in ascending order of the cost сk, and include them in the schedule (Hamilton circuit). – Add the other hypotheses ( ) to this sequence in descending order of the contribution dk. In other words, we should first test the hypotheses whose cost is less than the contribution to the experience, arranging them from simple to complex. Then we should proceed to the hypotheses whose contribution to the experience is smaller than the cost, arranging them in descending order of the contribution. Of course, the assumptions about the “additive” complexity of the experience are strong enough. On the other hand, these assumptions allow obtaining a simple analytical solution with a practical interpretation. Generally speaking, discrete optimization and graph theory provide a wide field for different problems of optimal hypothesis testing (author is grateful to Prof. Vladimir Burkov for some ideas and discussion); for example, the following formulations are possible based on the well-known results [7, 0]: • The knapsack problem with the synergistic effect: adding two items to the knapsack (including two topics in the research plan, or deciding to test two hypotheses) reduces their total weight (the total time to deal with them). It is required to develop a research plan that maximizes the accumulated experience (the amount of scientific knowledge) under cost constraints (labor-intensiveness). • The editor problem: for example, two researchers test a given set of hypotheses (a theoretician and a programmer). The theoretician develops a testing method, whereas the programmer develops testing software. After that, the theoretician conducts computational experiments based on this software. It is required to determine a schedule to test hypotheses that minimizes the total test time. • The assignment problem: there are n hypotheses (scientific problems) and m researchers, where . The competencies of all researchers to solve these problems (to test the corresponding hypotheses) are known. It is required to assign one researcher to each hypothesis so that the total (or maximum) test time for all hypotheses achieves minimum. (The test time depends on the researcher’s competence.) 1 1 k k j j D d - = =å 1 1 k k j j С С - = =å k k k kc C Dg = + - 1 ( ) max{ } kik ,K g r g = = ( ) min r g r ® k kd c³ k kd c< m n³ OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 125 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) APPENDIX Proof of Lemma 1. Assume on the contrary that . Since the function is concave, . Hence, , which finally implies due to the strict monotonicity of the function . This contradiction completes the proof. Proof of Proposition 1. First, note that interchanging hypotheses j and j + 1 will not modify the sets Nl for all l from 1 to j – 1 and from j + 2 to K. Therefore, it will not change the test times of all hypotheses except j and j + 1. This fact is essential for the other propositions. We compare the total test times of hypotheses j and j + 1: and . The first sum is equal to Tj, j+1 = . The second sum is equal to Tj+1, j = . Assume on the contrary that Tj+1, j ≥ Tj, j+1. In view of , we obtain ≤ . We rewrite this inequality as ≤ . Since , the left-hand side is strictly positive. Hence, the right-hand side has the same property: > 0. As the denominator is strictly positive, the numerator is such as well: > 1. Therefore, , which contradicts item a) of Lemma 2. Proof of Proposition 2. We compare the total test times of hypotheses j and j + 1: and . ( ) ( )x y x z y z y y+ + £ ( )y × ( ) ( ) ( ( ) ( )) /x y x x z x y z y y y y y y+ + + - ³ ( ) ( ) ( ) ( )x x z x x z y z z z y y y y+ + + - £ z y£ ( )y × 1 1( , ( )) + ( , ( ))j j j j j j jT w T w we y h e y h+ + + 1 1 1( , ( )) + ( , ( ))j j j j j j jT w T w we y h e y h+ + ++ ( ) ( )0 1 1 1ln( ) 1 ln 1 ( ) ln 1 ( )j j j j jL w w w e y h y h+ é ù +ê ú - - - +ê úë û ( ) ( )0 1 1 1 1ln( ) 1 ln 1 ( ) ln 1 ( )j j j j jL w w w e y h y h+ + é ù +ê ú - - - +ê úë û 0ln( ) 0 1 L e < - ( ) ( )1 1 1 1 ln 1 ( ) ln 1 ( )j j j j jw w wy h y h+ + + - - + ( ) ( )1 1 1 ln 1 ( ) ln 1 ( )j j j j jw w wy h y h+ + - - + ( ) ( )1 1 1 ln 1 ( ) ln 1 ( )j j j jw wy h y h+ - - - ( ) ( )1 1 1 1 ln 1 ( ) ln 1 ( )j j j j j jw w w wy h y h+ + - - + - + 1j jw w +< ( ) ( ) 1 1 1 1 1 ( ) ln 1 ( ) ln 1 ( ) ln 1 ( ) j j j j j j j j j j j j w w w w w w w w y h y h y h y h + + + + æ ö- + ç ÷ç ÷- +è ø - + - + 1 1 1 ( ) 1 ( ) j j j j j j w w w w y h y h + + - + - + 1 1 ( ) ( )j j j j j j w w w w y h y h+ + + + < 1 1( , ( )) + ( , ( ))j j j j j j jT w T w we y h e y h+ + + 1 1 1( , ( )) + ( , ( ))j j j j j j jT w T w we y h e y h+ + ++ 126 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) The first sum is equal to Tj, j+1 = . The second sum is equal to Tj+1, j = . Assume on the contrary that Tj+1, j ≥ Tj, j+1. In view of , we obtain ≤ . We rewrite this inequality as ≤ . Since , the left-hand side is strictly positive. Hence, the right-hand side has the same property: > 0. As the denominator is strictly positive, the numerator is such as well: > 1. Therefore, , which contradicts condition (11) of Assumption A.2. Proof of Proposition 3. Let . From the condition of this proposition it follows that . We compare the total expected test times of hypotheses j and j + 1: and . The first sum is equal to Tj, j+1 = + . The second sum is equal to Tj+1, j = + . Assume on the contrary that Tj+1, j ≥ Tj, j+1. Then Tj+1, j - Tj, j+1 ≥ 0, and ( ) ( )0 1 1 1ln( ) 1 ln 1 ( ) ln 1 ( )j j j j jL w w w e y h y h+ é ù +ê ú - - - - - +ê úë û ( ) ( )0 1 1 1 1ln( ) 1 ln 1 ( ) ln 1 ( )j j j j jL w w w e y h y h+ + é ù +ê ú - - - - - +ê úë û 0ln( ) 0 1 L e < - ( ) ( )1 1 1 1 ln 1 ( ) ln 1 ( )j j j j jw w wy h y h+ + + - - - - + ( ) ( )1 1 1 ln 1 ( ) ln 1 ( )j j j j jw w wy h y h+ + - - - - + ( ) ( )1 1 1 ln 1 ( ) ln 1 ( )j j j jw wy h y h+ - - - - - ( ) ( )1 1 1 1 ln 1 ( ) ln 1 ( )j j j j j jw w w wy h y h+ + - - - + - - + 1j jw w +< ( ) ( ) 1 1 1 1 1 ( ) ln 1 ( ) ln 1 ( ) ln 1 ( ) j j j j j j j j j j j j w w w w w w w w y h y h y h y h + + + + æ ö- - + ç ÷ç ÷- - +è ø - - + - - + 1 1 1 ( ) 1 ( ) j j j j j j w w w w y h y h + + - - + - - + 1 1( ) ( )j j j j j jw w w wy h y h+ ++ - + < - 0 1 (0) j' j j w w L = > - 1 ' ' j jw w +< 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + + 1 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + ++ 1 ( )' j jw y h 1 1 ( )' j j jw wy h+ + 1 1 ( )' j jw y h+ 1 1 ( )' j j jw wy h ++ OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 127 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) + - - ≥ 0. Due to Assumption A.3 and , we can estimate the denominator of the second term as: + > 0, > 0, > 0. Since , the numerator of the first factor is strictly negative whereas the denominator is strictly positive. By Assumption А.3, the numerator and denominator of the second factor are strictly positive. This contradiction completes the proof. Proof of Proposition 4. We compare the total expected test times of hypotheses j and j + 1: and . The first sum is equal to Tj, j+1 = + . The second sum is equal to Tj+1, j = + . Assume on the contrary that Tj+1, j ≥ Tj, j+1. Then Tj+1, j - Tj, j+1 ≥ 0, and - + - ≥ 0. Trivial transformations, particularly cancelation by the strictly positive value , yield - ≥ 0. The denominators of both fractions are strictly positive as the products of strictly positive values. Since , the numerator of the first fraction is strictly negative. Hence, this fraction has the same property as well. The numerator of the second fraction is nonnegative due to condition (11) of Assumption A.2. Therefore, the entire difference of these strictly negative and nonnegative values is strictly negative. This contradiction completes the proof. Proof of Proposition 5. We compare the total expected test times of hypotheses j and j + 1: and . The first sum is equal to Tj, j+1 = + , The second sum is equal to Tj+1, j = + . 1 1 ( )' j jw y h+ 1 1 ( )' j j jw wy h ++ 1 ( )' j jw y h 1 1 ( )' j j jw wy h+ + 1j jw w +< 1 1 1 1 ( )' ' j j jw w y h+ æ ö -ç ÷ç ÷ è ø 1 1 1 1 ( )' ' j j j jw w wy h+ æ ö -ç ÷ç ÷ +è ø 1 1 1 1 1 ( ) ( )' ' j j j j jw w wy h y h+ æ öæ ö - -ç ÷ç ÷ç ÷ç ÷+è øè ø 1 1 ( ) ( ) ( ) ( ) ' ' j j j j j ' ' j j j j j w w w w w w y h y h y h y h + + æ öæ ö- + - ç ÷ç ÷ç ÷ç ÷+è øè ø 1j jw w +< 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + + 1 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + ++ 01 ( )j j L w y h - + 0 1 1 ( )j j j L w wy h+ - + + 0 1 1 ( )j j L w y h+ - + 0 1 1 ( )j j j L w wy h + - + + 0 1 1 ( )j j L w y h+ - + 01 ( )j j L w y h - + 0 1 1 ( )j j j L w wy h + - + + 0 1 1 ( )j j j L w wy h+ - + + 01 L- 1 1( ( ))( ( )) j j j j j j w w w wy h y h + + - + + 1 1 1 1 ( ) ( ) ( ( ))( ( )) j j j j j j j j j j j j w w w w w w w w y h y h y h y h + + + + + - + + - + + + + 1j jw w +< 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + + 1 1 1( ( )) + ( ( ))j j j j j j jw w wt y h t y h+ + ++ 01 ( )j j L w y h - 0 1 1 ( )j j j L w wy h+ - + 0 1 1 ( )j j L w y h+ - 0 1 1 ( )j j j L w wy h + - + 128 D. NOVIKOV Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) Assume on the contrary that Tj+1, j ≥ Tj, j+1. Then Tj+1, j - Tj, j+1 ≥ 0, and + - - ≥ 0. Since and the function is decreasing, we cancel by the strictly positive value and estimate the denominator of the second term as: - > 0, > 0, > 0. Since , the numerator and denominator of the first factor are strictly positive. Since and the function is strictly decreasing, the numerator of the second factor is strictly negative whereas the denominator of the second factor is strictly positive. This contradiction completes the proof. Proof of Proposition 6. We compare the total expected test times of hypotheses j and j + 1: and . The first sum is equal to Tj, j+1 = + , The second sum is equal to Tj+1, j = + . Assume on the contrary that Tj+1, j ≥ Tj, j+1. Then Tj+1, j - Tj, j+1 ≥ 0, and + - - ≥ 0. + ≥ 0. Since and the function is strictly monotonic, we have the estimate + < < 0. This contradiction completes the proof. REFERENCES 1. Belov, M.; Novikov, D. (2020) Methodology of Complex Activity: Foundations of Understanding and Modelling; Springer: Heidelberg, 2020. 2. Belov, M.; Novikov, D. (2021) The Structure of Creative Activity. Control Sciences, 5. 17-28. 3. Gupta, B.; Gupta, N. (2021) Research methodology; SBPD Publications: Agra. 4. Rao, D.; Rao, J. (2019) Research methodology; Himalaya Publishing House: Nagpur. 5. Belov, M.; Novikov, D. (2021) Models of Experience. Control Sciences, 1, 43–60. 0 1 1 ( )j j L w y h+ - 0 1 1 ( )j j j L w wy h + - + 01 ( )j j L w y h - 0 1 1 ( )j j j L w wy h+ - + 1j jw w +> ( )y × 01 L- 1 1 1 1 ( )j j jw w y h+ æ ö -ç ÷ç ÷ è ø 1 1 1 1 ( )j j j jw w wy h+ æ ö -ç ÷ç ÷ +è ø 1 1 1 1 1 ( ) ( )j j j j jw w wy h y h+ æ öæ ö - -ç ÷ç ÷ç ÷ç ÷+è øè ø 1 1 ( ) ( ) ( ) ( ) j j j j j j j j j j w w w w w w y h y h y h y h + + æ öæ ö- + - ç ÷ç ÷ç ÷ç ÷+è øè ø 1j jw w +> 1j jw w +> ( )y × 1 1( ( ), ) + ( ( ), )j j j j j j jw w wt z h t z h+ ++ 1 1( ( ), ) + ( ( ), )j j j j j j jw w wt z h t z h+ + + 1 ( )j jw z h- 1 1 ( )j j j w w z h + - + 1 1 ( )j jw z h + - 11 ( )j j j w w z h +- + 1 1 ( )j jw z h + - 11 ( )j j j w w z h +- + 1 ( )j jw z h- 1 1 ( )j j j w w z h + - + 1( ) ( )j j j j w w z h z h +- + 1 ( ) ( )j j j j w w z h z h + + - 1j jw w +< ( )z × 1( ) ( )j j j j w w z h z h +- + 1 ( ) ( )j j j j w w z h z h + + - 1( ) ( )j j j j j w w w z h z h ++ - + OPTIMAL SCHEDULE TO TEST INDEPENDENT HYPOTHESES 129 Copyright ©2021 ASSA. Adv. in Systems Science and Appl. (2021) 6. Belov, M.; Novikov, D. (2021) Optimal Enterprise: Structures, Processes and Mathematics of Knowledge, Technology and Human Capital; CRC Press: Boca Raton. 7. Brucker, P. (2007) Scheduling Algorithms, 5th ed.; Springer: Berlin. 8. Pinedo, M. (2002) Scheduling: Theory, Algorithms, and Systems. Prentice-Hall: Upper Saddle River. 9. Koulamas, C.; Kyparisis, G. (2008) Single-machine scheduling problems with past- sequence-dependent setup times. Eur. J. Oper. Res. 187, 1045–1049. 10. Browne, S.; Yechiali, U. (1990) Scheduling deteriorating jobs on a single processor. Operations Research, 38(3), 495–498. 11. Sun, J; Li, Y. (2013) Single-machine scheduling with past-sequence-dependent delivery times and deteriorating jobs. Mathematica Aeterna, 3(9), 799–806. 12. Lee, W.; Lai, P.; Wu, C. (2011) Some single-machine and flowshop scheduling problems with a non-linear deterioration function. Computers and Mathematics with Applications, 62, 2487–2496. 13. Koulamas, C.; Kyparisis, G. (2019) New results for single-machine scheduling with past-sequence-dependent setup times and due date-related objectives. Eur. J. Oper. Res., 278, 149–159. 14. Wang, L.; Huang, W.; Liu, W.; et al. (2021) Scheduling with position-dependent weights, due-date assignment and past-sequence-dependent setup times. RAIRO-Oper. Res. 55, 2747–2758. 15. Biskup, D. (1999) Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173–178. 16. Cheng, E.; Kovalyov, M. (1994) Scheduling with learning effects on job processing times. Working Paper No. 06/94. The Hong Kong Polytechnic University. 17. Cheng, E.; Wang, G. (2000) Single machine scheduling with learning effect considerations. Annals of Operations Research, 98, 273–290. 18. Wang, L.; Wang, J.; Feng, E. (2011) Scheduling jobs with general learning functions. J. Syst. Sci. Syst. Eng. 20(1), 119–125. 19. Wang, X.; Wang, J. (2013) Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning. Applied Mathematical Modelling, 37, 4905–4914. 20. Low, C.; Lin, W. (2013) Some scheduling problems with time-dependent learning effect and deteriorating jobs. Applied Mathematical Modelling, 37, 8865–8875. 21. Bessy, S.; Giroudeau, R. (2019) Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, 22(3), 305–313. 22. Khatami, M.; Salehipour, A. (2021) Coupled task scheduling with time-dependent processing times. Journal of Scheduling, 24, 223–236. 23. Wu C. et al. (2021) Cloud theory-based simulated annealing for a single-machine past sequence setup scheduling with scenario-dependent processing times. Complex & Intelligent Systems. 7, 345–357. 24. Gawiejnowicz, S.; Kurc, W. (2020) New results for an open time-dependent scheduling problem. Journal of Scheduling, 23, 733–744. 25. Zhang, Xin-Gong & Bai, Dan-Yu & Win-Chin, Lin & Cheng, Shuenn-Ren & Wu, Chin- Chia. (2021) Single-machine slack due-window assignment scheduling with multiple maintenance activities and position-and-resource-dependent processing times. International Journal of Systems Science: Operations & Logistics. 10. 1-12. 26. The Traveling Salesman Problem and Its Variations (2007), Gutin, G. and Punnen, A., Eds. Springer: New York. 27. Chentsov, A.G.; Chentsov, A.A. (2016) Routing under constraints: problem of visit to megalopolises. Autom. Remote Control, 77(11), 1957–1974. 28. Burkov, V.; et al. (2013) Mechanism Design and Management: Mathematical Methods for Smart Organizations; Nova Science Publishers: New York.