300

(the line ends with a line-feed character)

• Line1: Length of work time frame is 300 (T_\text{max}=300).

14 19
1 7 1
1 2 1
2 9 1
2 3 1
3 5 1
3 7 1
3 6 1
4 13 2
4 10 2
4 6 1
4 5 1
6 8 1
7 8 1
8 14 2
9 11 2
10 12 2
10 11 2
12 13 2
13 14 2

(The last line ends with a line-feed character)

• Line 1: The graph has 14 vertices and 19 edges(N_V=14,N_E=19).
  • Vertex indices from 1 to 14 are assigned to these 14 vertices.
  • Below, the vertex corresponding to vertex indices i will be referred to simply as vertex i.
• Line 2: There is an edge of length 1 between vertices 1 and 7(u_{1}=1,v_{1}=7,d_{1}=1).
• Line 3: There is an edge of length 1 between vertices 1 and 2(u_{2}=1,v_{2}=2,d_{2}=1).
• Line 4: There is an edge of length 1 between vertices 2 and 9(u_{3}=2,v_{3}=9,d_{3}=1).
• Line 5: There is an edge of length 1 between vertices 2 and 3(u_{4}=2,v_{4}=3,d_{4}=1).
• Line 6: There is an edge of length 1 between vertices 3 and 5(u_{5}=3,v_{5}=5,d_{5}=1).
• Line 7: There is an edge of length 1 between vertices 3 and 7(u_{6}=3,v_{6}=7,d_{6}=1).
• Line 8: There is an edge of length 1 between vertices 3 and 6(u_{7}=3,v_{7}=6,d_{7}=1).
• Line 9: There is an edge of length 2 between vertices 4 and 13(u_{8}=4,v_{8}=13,d_{8}=2).
• Line 10: There is an edge of length 2 between vertices 4 and 10(u_{9}=4,v_{9}=10,d_{9}=2).
• Line 11: There is an edge of length 1 between vertices 4 and 6(u_{10}=4,v_{10}=6,d_{10}=1).
• Line 12: There is an edge of length 1 between vertices 4 and 5(u_{11}=4,v_{11}=5,d_{11}=1).
• Line 13: There is an edge of length 1 between vertices 6 and 8(u_{12}=6,v_{12}=8,d_{12}=1).
• Line 14: There is an edge of length 1 between vertices 7 and 8(u_{13}=7,v_{13}=8,d_{13}=1).
• Line 15: There is an edge of length 2 between vertices 8 and 14(u_{14}=8,v_{14}=14,d_{14}=2).
• Line 16: There is an edge of length 2 between vertices 9 and 11(u_{15}=9,v_{15}=11,d_{15}=2).
• Line 17: There is an edge of length 2 between vertices 10 and 12(u_{16}=10,v_{16}=12,d_{16}=2).
• Line 18: There is an edge of length 2 between vertices 10 and 11(u_{17}=10,v_{17}=11,d_{17}=2).
• Line 19: There is an edge of length 2 between vertices 12 and 13(u_{18}=12,v_{18}=13,d_{18}=2).
• Line 20(=1+N_E): There is an edge of length 2 between vertices 13 and 14(u_{19}=13,v_{19}=14,d_{19}=2).

5
6 100 3 1 2 3
13 59 1 3
10 55 2 2 3
9 47 3 1 2 3
9 89 1 2

(The last line ends with a line-feed character)

• Line 1: There are 5 workers (N_{\text{worker}}=5).
• Line 2: The descriptor for worker with ID=1.
  • The worker’s initial location is the vertex with vertex index 6 (v^{\text{init}}_1=6).
  • The maximum number of tasks this worker can perform per unit of time is 100 (L^{\text{max}}_1=100).
  • The worker can perform 3 types of job (N^{\text{JobType}}_1=3), of types 1, 2, 3 (\text{Type}^1_1=1,\text{Type}^1_2=2,\text{Type}^1_3=3).
• Line 3: The descriptor for worker with ID=2.
  • The worker’s initial location is the vertex with vertex index 13 (v^{\text{init}}_2=13).
  • The maximum number of tasks this worker can perform per unit of time is 59 (L^{\text{max}}_2=59).
  • The worker can perform 1 types of job (N^{\text{JobType}}_2=1), of type 3 (\text{Type}^2_1=3).
• Line 4: The descriptor for worker with ID=3.
  • The worker’s initial location is the vertex with vertex index 10 (v^{\text{init}}_3=10).
  • The maximum number of tasks this worker can perform per unit of time is 55 (L^{\text{max}}_3=55).
  • The worker can perform 2 types of job (N^{\text{JobType}}_3=2), of types 2, 3 (\text{Type}^3_1=2,\text{Type}^3_2=3).
• Line 5: The descriptor for worker with ID=4.
  • The worker’s initial location is the vertex with vertex index 9 (v^{\text{init}}_4=9).
  • The maximum number of tasks this worker can perform per unit of time is 47 (L^{\text{max}}_4=47).
  • The worker can perform 3 types of job (N^{\text{JobType}}_4=3), of types 1, 2, 3 (\text{Type}^4_1=1,\text{Type}^4_2=2,\text{Type}^4_3=3).
• Line 6(=1+N_{\text{worker}}): The descriptor for worker with ID=5.
  • The worker’s initial location is the vertex with vertex index 9 (v^{\text{init}}_5=9).
  • The maximum number of tasks this worker can perform per unit of time is 89 (L^{\text{max}}_5=89).
  • The worker can perform 1 types of job (N^{\text{JobType}}_5=1), of type 2 (\text{Type}^5_1=2).

• Tasks cannot be processed during time intervals when reward is not available (when the reward per unit task is zero).
• The number of tasks that a worker is able to perform per unit time is affected by the weather (Constraints on tasks performed)
• Jobs that have not been accepted cannot be performed.

In other words, given a list of control points, p=((t_i,y_i))_{i=1,\cdots,n} (t_i,y_i\in \mathbb{Z},t_1 < t_2 < \cdots < t_n,n\geq 1), the per-task reward at time t function r(t) (actually r(t;p)), is defined as:

r(t)=\begin{cases} y_1, & \text{if}\,\, t < t_1, \\ y_n, & \text{if}\,\, t \geq t_n, \\ (y_\text{next}-y_\text{prev})(t-t_\text{prev})/(t_\text{next}-t_\text{prev})+y_\text{prev}, & \text{otherwise}. \end{cases}

Here, (t_\text{prev},y_\text{prev}) is the pair with the largest time that does not exceed t, and (t_\text{next},y_\text{next}) is the pair with the smallest time that exceeds t.

r(t), integral multiples of r(t) and their sum are computed in decimals.

6
1 1 906 10 0.94469412898840599 0.07857326752336613 0
13 11 0 12 1212810 37 1849941 63 2266874 88 1944271 113 1207029 139 768959 164 808665 189 992126 214 1137116 240 907954 265 903397 266 0
0
2 3 905 2 0.96478158647239831 0.056877102556647817 0
7 92 0 93 1280499 121 1553205 149 1429506 176 1419189 204 1731967 205 0
0
3 1 1052 4 0.94436951517275258 0.071240847781028308 0
7 191 0 192 1914094 218 1735762 244 1444725 270 1275768 296 975408 297 0
0
4 3 653 4 0.95274950239675604 0.14137003825803521 0
10 70 0 71 1319303 94 1329844 118 1503315 141 1161131 165 1294526 188 849137 212 1953166 235 2087503 236 0
1 2
5 1 1452 12 0.95747093286627682 0.076042573628832266 0
8 122 0 123 1667665 149 911519 174 1511934 200 1967913 225 1633211 251 1589845 252 0
2 6 4
6 2 737 6 0.95812926774107732 0.049371044631834608 1
11 82 0 83 1431723 108 1475010 133 1032345 158 1012865 183 1593586 207 1923638 232 1956884 257 2797127 282 2877123 283 0
0

• Line 1: The total number of jobs is 6. (N_{\text{job}}=6)
  • The actual problem given will consist of several hundreds of jobs.
• Line 2: Start of description for job with ID=1.
  • The job ID is 1 (\text{ID}^{\text{job}}_1=1).
  • The job type is 1 (\text{Type}_1=1).
  • The number of tasks required to complete this job is 906 (N^{\text{task}}_1=906).
  • The job is located at vertex 10 (v^{\text{job}}_1=10).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.94469412898840599 will be applied (Scoring method) (P^{\text{job}}_1=0.94469412898840599).
  • Dependency of this job on weather is 0.07857326752336613 (Limits on tasks performed) (d^\text{weather}_1=0.07857326752336613).
  • This job is not mandatory (f^{\text{mandatory}}_1=0).
• Line 3: Definition of reward function for the job with ID=1.
  • There are 13 control points (N^{\text{reward}}_1=13).
  • The list of control points is: ((11,0), (12,1212810), (37,1849941), (63,2266874), (88,1944271), (113,1207029), (139,768959), (164,808665), (189,992126), (214,1137116), (240,907954), (265,903397), (266,0)).
    • The times for which reward can be obtained are 12,13,\cdots,265.
• Line 4: The jobs that the job with ID=1 depends on. This completes the description of the job with ID=1.
  • The number of jobs this job depends on is 0(N^{\text{depend}}_1=0).
  • (Since the number of jobs it depends on is 0, no job IDs are given.)
• Line 5: Start of description for job with ID=2.
  • The job ID is 2 (\text{ID}^{\text{job}}_2=2).
  • The job type is 3 (\text{Type}_2=3).
  • The number of tasks required to complete this job is 905 (N^{\text{task}}_2=905).
  • The job is located at vertex 2 (v^{\text{job}}_2=2).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.96478158647239831 will be applied (Scoring method) (P^{\text{job}}_2=0.96478158647239831).
  • Dependency of this job on weather is 0.056877102556647817 (Limits on tasks performed) (d^\text{weather}_2=0.056877102556647817).
  • This job is not mandatory (f^{\text{mandatory}}_2=0).
• Line 6: Definition of reward function for the job with ID=2.
  • There are 7 control points (N^{\text{reward}}_2=7).
  • The list of control points is: ((92,0), (93,1280499), (121,1553205), (149,1429506), (176,1419189), (204,1731967), (205,0)).
    • The times for which reward can be obtained are 93,94,\cdots,204.
• Line 7: The jobs that the job with ID=2 depends on. This completes the description of the job with ID=2.
  • The number of jobs this job depends on is 0(N^{\text{depend}}_2=0).
  • (Since the number of jobs it depends on is 0, no job IDs are given.)
• Line 8: Start of description for job with ID=3.
  • The job ID is 3 (\text{ID}^{\text{job}}_3=3).
  • The job type is 1 (\text{Type}_3=1).
  • The number of tasks required to complete this job is 1052 (N^{\text{task}}_3=1052).
  • The job is located at vertex 4 (v^{\text{job}}_3=4).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.94436951517275258 will be applied (Scoring method) (P^{\text{job}}_3=0.94436951517275258).
  • Dependency of this job on weather is 0.071240847781028308 (Limits on tasks performed) (d^\text{weather}_3=0.071240847781028308).
  • This job is not mandatory (f^{\text{mandatory}}_3=0).
• Line 9: Definition of reward function for the job with ID=3.
  • There are 7 control points (N^{\text{reward}}_3=7).
  • The list of control points is: ((191,0), (192,1914094), (218,1735762), (244,1444725), (270,1275768), (296,975408), (297,0)).
    • The times for which reward can be obtained are 192,193,\cdots,296.
• Line 10: The jobs that the job with ID=3 depends on. This completes the description of the job with ID=3.
  • The number of jobs this job depends on is 0(N^{\text{depend}}_3=0).
  • (Since the number of jobs it depends on is 0, no job IDs are given.)
• Line 11: Start of description for job with ID=4.
  • The job ID is 4 (\text{ID}^{\text{job}}_4=4).
  • The job type is 3 (\text{Type}_4=3).
  • The number of tasks required to complete this job is 653 (N^{\text{task}}_4=653).
  • The job is located at vertex 4 (v^{\text{job}}_4=4).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.95274950239675604 will be applied (Scoring method) (P^{\text{job}}_4=0.95274950239675604).
  • Dependency of this job on weather is 0.14137003825803521 (Limits on tasks performed) (d^\text{weather}_4=0.14137003825803521).
  • This job is not mandatory (f^{\text{mandatory}}_4=0).
• Line 12: Definition of reward function for the job with ID=4.
  • There are 10 control points (N^{\text{reward}}_4=10).
  • The list of control points is: ((70,0), (71,1319303), (94,1329844), (118,1503315), (141,1161131), (165,1294526), (188,849137), (212,1953166), (235,2087503), (236,0)).
    • The times for which reward can be obtained are 71,72,\cdots,235.
• Line 13: The jobs that the job with ID=4 depends on. This completes the description of the job with ID=4.
  • The number of jobs this job depends on is 1(N^{\text{depend}}_4=1).
  • This job depends on the job with ID=2(\text{id}^\text{depend}_{4,1}=2).
• Line 14: Start of description for job with ID=5.
  • The job ID is 5 (\text{ID}^{\text{job}}_5=5).
  • The job type is 1 (\text{Type}_5=1).
  • The number of tasks required to complete this job is 1452 (N^{\text{task}}_5=1452).
  • The job is located at vertex 12 (v^{\text{job}}_5=12).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.95747093286627682 will be applied (Scoring method) (P^{\text{job}}_5=0.95747093286627682).
  • Dependency of this job on weather is 0.076042573628832266 (Limits on tasks performed) (d^\text{weather}_5=0.076042573628832266).
  • This job is not mandatory (f^{\text{mandatory}}_5=0).
• Line 15: Definition of reward function for the job with ID=5.
  • There are 8 control points (N^{\text{reward}}_5=8).
  • The list of control points is: ((122,0), (123,1667665), (149,911519), (174,1511934), (200,1967913), (225,1633211), (251,1589845), (252,0)).
    • The times for which reward can be obtained are 123,124,\cdots,251.
• Line 16: The jobs that the job with ID=5 depends on. This completes the description of the job with ID=5.
  • The number of jobs this job depends on is 2(N^{\text{depend}}_5=2).
  • This job depends on the jobs with ID=6,4(\text{id}^\text{depend}_{5,1}=6,\text{id}^\text{depend}_{5,2}=4).
• Line 17: Start of description for job with ID=6.
  • The job ID is 6 (\text{ID}^{\text{job}}_6=6).
  • The job type is 2 (\text{Type}_6=2).
  • The number of tasks required to complete this job is 737 (N^{\text{task}}_6=737).
  • The job is located at vertex 6 (v^{\text{job}}_6=6).
  • If this job is accepted, but not finished by the end of the work time frame (T_\text{max}), an unfinished-job penalty of 0.95812926774107732 will be applied (Scoring method) (P^{\text{job}}_6=0.95812926774107732).
  • Dependency of this job on weather is 0.049371044631834608 (Limits on tasks performed) (d^\text{weather}_6=0.049371044631834608).
  • This job is mandatory (f^{\text{mandatory}}_6=1).
• Line 18: Definition of reward function for the job with ID=6.
  • There are 11 control points (N^{\text{reward}}_6=11).
  • The list of control points is: ((82,0), (83,1431723), (108,1475010), (133,1032345), (158,1012865), (183,1593586), (207,1923638), (232,1956884), (257,2797127), (282,2877123), (283,0)).
    • The times for which reward can be obtained are 83,84,\cdots,282.
• Line 19(=1+3\times N_{\text{job}}): The jobs that the job with ID=6 depends on. This completes the description of the job with ID=6.
  • The number of jobs this job depends on is 0(N^{\text{depend}}_6=0).
  • (Since the number of jobs it depends on is 0, no job IDs are given.)

Fundamental Weather

The total length of work time frame is divided equally into fundamental weather segments, b_i (i=1,\cdots,n(=T_\text{max}/T^\text{weather})), of length T^\text{weather}.

Each b_i has an independent weather state, w_i, which is called the fundamental weather state.

At time point t=1, all w_i are determined probabilistically and independently according to the stationary distribution of the transition probability matrix. Thereafter, every time T^\text{weather} time elapses, w_i in each segment is updated independently according to the transition probability matrix.

Actual Weather State

Here we call the actual weather state w. w is updated as follows:

At the beginning of time t,

• if t equals the start time of weather segment b_i :w \leftarrow w_i (set w to w_i)
• In other cases:update w according to the transition probability matrix.

Note that updating of fundamental weather state is performed before updating the actual weather state.

When weather (value or state) is mentioned in other sections, it refers to the actual weather state, w.

The seed value used to determine the weather is given a different value for each test case.

10 7
0.65038945819291316 0.3456395688250497 0.0039709729820371371 0 0 0 0
0.29367291714300126 0.57978625074387669 0.11253142456916906 0.014009407543952863 0 0 0
1.4131189430426344e-09 0.18905960051799561 0.44909739165434842 0.32239542530231813 0.039447581112218938 0 0
0 0.043752041690362654 0.079271361143687852 0.87011603340370036 0.0033077052290538069 0.0035528585331954204 0
0 0 0.015190350742277408 0.044334491311077411 0.90080171493640016 0.039640375730251982 3.3067279992976463e-05
0 0 0 2.9123680876183852e-09 0.21976983161374733 0.68711791872304939 0.093112246750835195
0 0 0 0 0.018677162951541051 0.41030647336908055 0.57101636367937847
0 1 2 3 10 14 20

• Line 1: The fundamental weather segment length is 10, and there are 7 weather states in total(T^\text{weather}=10,N^\text{weather}=7).
• Line 2: The (fundamental) transition probabilities from state 1 to states 1,2,3,4,5,6,7 are:0.65038945819291316,0.3456395688250497,0.0039709729820371371,0,0,0,0, respectively.
• Line 3: The (fundamental) transition probabilities from state 2 to states 1,2,3,4,5,6,7 are:0.29367291714300126,0.57978625074387669,0.11253142456916906,0.014009407543952863,0,0,0, respectively.
• Line 4: The (fundamental) transition probabilities from state 3 to states 1,2,3,4,5,6,7 are:1.4131189430426344e-09,0.18905960051799561,0.44909739165434842,0.32239542530231813,0.039447581112218938,0,0, respectively.
• Line 5: The (fundamental) transition probabilities from state 4 to states 1,2,3,4,5,6,7 are:0,0.043752041690362654,0.079271361143687852,0.87011603340370036,0.0033077052290538069,0.0035528585331954204,0, respectively.
• Line 6: The (fundamental) transition probabilities from state 5 to states 1,2,3,4,5,6,7 are:0,0,0.015190350742277408,0.044334491311077411,0.90080171493640016,0.039640375730251982,3.3067279992976463e-05, respectively.
• Line 7: The (fundamental) transition probabilities from state 6 to states 1,2,3,4,5,6,7 are:0,0,0,2.9123680876183852e-09,0.21976983161374733,0.68711791872304939,0.093112246750835195, respectively.
• Line 8: The (fundamental) transition probabilities from state 7 to states 1,2,3,4,5,6,7 are:0,0,0,0,0.018677162951541051,0.41030647336908055,0.57101636367937847, respectively.
• Line 9: The limit constants for states 1,2,3,4,5,6,7 are:0,1,2,3,10,14,20, respectively.

0.029878077064496654 0.99054720249346828 0.87563809736779619

• Line 1: The maximum schedule change penalty is 0.029878077064496654, the schedule change penalty decay rate is 0.99054720249346828, and the schedule additional point coefficient is 0.87563809736779619.(P_m=0.029878077064496654,R_m=0.99054720249346828,\alpha=0.87563809736779619)

300
14 19
1 7 1
1 2 1
2 9 1
2 3 1
3 5 1
3 7 1
3 6 1
4 13 2
4 10 2
4 6 1
4 5 1
6 8 1
7 8 1
8 14 2
9 11 2
10 12 2
10 11 2
12 13 2
13 14 2
5
6 100 3 1 2 3
13 59 1 3
10 55 2 2 3
9 47 3 1 2 3
9 89 1 2
6
1 1 906 10 0.94469412898840599 0.07857326752336613 0
13 11 0 12 1212810 37 1849941 63 2266874 88 1944271 113 1207029 139 768959 164 808665 189 992126 214 1137116 240 907954 265 903397 266 0
0
2 3 905 2 0.96478158647239831 0.056877102556647817 0
7 92 0 93 1280499 121 1553205 149 1429506 176 1419189 204 1731967 205 0
0
3 1 1052 4 0.94436951517275258 0.071240847781028308 0
7 191 0 192 1914094 218 1735762 244 1444725 270 1275768 296 975408 297 0
0
4 3 653 4 0.95274950239675604 0.14137003825803521 0
10 70 0 71 1319303 94 1329844 118 1503315 141 1161131 165 1294526 188 849137 212 1953166 235 2087503 236 0
1 2
5 1 1452 12 0.95747093286627682 0.076042573628832266 0
8 122 0 123 1667665 149 911519 174 1511934 200 1967913 225 1633211 251 1589845 252 0
2 6 4
6 2 737 6 0.95812926774107732 0.049371044631834608 1
11 82 0 83 1431723 108 1475010 133 1032345 158 1012865 183 1593586 207 1923638 232 1956884 257 2797127 282 2877123 283 0
0
10 7
0.65038945819291316 0.3456395688250497 0.0039709729820371371 0 0 0 0
0.29367291714300126 0.57978625074387669 0.11253142456916906 0.014009407543952863 0 0 0
1.4131189430426344e-09 0.18905960051799561 0.44909739165434842 0.32239542530231813 0.039447581112218938 0 0
0 0.043752041690362654 0.079271361143687852 0.87011603340370036 0.0033077052290538069 0.0035528585331954204 0
0 0 0.015190350742277408 0.044334491311077411 0.90080171493640016 0.039640375730251982 3.3067279992976463e-05
0 0 0 2.9123680876183852e-09 0.21976983161374733 0.68711791872304939 0.093112246750835195
0 0 0 0 0.018677162951541051 0.41030647336908055 0.57101636367937847
0 1 2 3 10 14 20
0.029878077064496654 0.99054720249346828 0.87563809736779619
1 0 0 0 0 1 0 0
11 0.32997661987364896 0.35720093880279286 0.10144180605929307 0.18397452127884667 0.023582674286464638 0.0033945272798704107 0.00042891241908338078
21 0.26146895868607978 0.29829553702903927 0.10367350846525671 0.27413103299772817 0.050432669277988201 0.010115966874572493 0.0018823266693354056
31 0.20903275687358913 0.2506351074109075 0.10197621041600768 0.32306215864825039 0.090561788952494518 0.020385340563280511 0.0043466371354700514
41 0.16453280991499084 0.20329129777873356 0.091390970778385427 0.30920472674724836 0.18000987309438846 0.041926491747270762 0.0096438299389825944
51 0.21773018584216544 0.25781470723187322 0.10129611879665416 0.30911960619088807 0.089756375035668315 0.020014729744938529 0.0042682771578124723
61 0.18695780159879197 0.22637031212950884 0.095692191594510659 0.30993166346993428 0.14119172380160475 0.032519854076175789 0.0073364533294737588
71 0.19978365794228928 0.23953773160128791 0.098109392505800377 0.31008680745444389 0.11925953673379487 0.027193693951331609 0.0060291798110520588
81 0.20381180897940113 0.24366400563862556 0.098856417213860404 0.3100620551039589 0.11244486750690874 0.02553797224640603 0.0056228733108393747
91 0.21098420754865557 0.2510068631469719 0.10018090439250056 0.30998380940692433 0.10034511870194431 0.02259771906125015 0.0049013777417531382
101 0.21017332149772244 0.25017760625955138 0.10003235653165234 0.30999988763169445 0.10170583135583394 0.022928465225827428 0.0049825314977181429
111 0.21035975914577648 0.25036818399930888 0.10006639945926016 0.30999551883837906 0.10139365148795368 0.02285257565351554 0.0049639114158061791
121 0.21006375850103443 0.25006523326156821 0.10001185087147714 0.3099994276865809 0.10189232028110375 0.022973761374232418 0.0049936480240032411
131 0.21003860874539299 0.25003947404099974 0.1000071910191422 0.30999960764692047 0.10193484214518268 0.022984093048729243 0.0049961833536327927
141 0.21002336947231043 0.25002386973415752 0.10000437307823702 0.30999975094869503 0.1019605735904045 0.022990345532450621 0.0049977176437451558
151 0.21001036314333912 0.25001055377029446 0.10000197057271488 0.30999988860662192 0.1019825193444605 0.022995678324735189 0.0049990262378340521
161 0.2098468891366603 0.24984320350327363 0.099971794472248382 0.31000174310451423 0.10225822676243579 0.023062676470061792 0.0050154665508059335
171 0.21001766063059757 0.25001802405322704 0.10000331731605842 0.30999980388842874 0.10197021368851594 0.022992687970461667 0.0049982924527108988
181 0.21000312608202204 0.25000314492830189 0.10000063442967058 0.30999996928440271 0.10199472644850339 0.022998644688091742 0.0049997541390076946
191 0.21000646152716931 0.25000655944481537 0.10000125010448897 0.30999993130167014 0.10198910119136487 0.022997277723427214 0.0049994187070641306
201 0.21000390597655963 0.25000394330415704 0.10000077837739391 0.30999996034571875 0.10199341120724155 0.022998325077383485 0.0049996757115455511
211 0.21000068372351638 0.25000064465305499 0.10000018358284854 0.30999999695861213 0.10199884564588058 0.022999645671209767 0.004999999764877615
221 0.21000123276535285 0.25000120671230119 0.10000028493014526 0.3099999907192631 0.10199791966912596 0.022999420654547454 0.0049999445492642201
231 0.2100001748189628 0.25000012368230085 0.10000008964391316 0.31000000273847578 0.10199970393318095 0.022999854238977081 0.0050000509441893055
241 0.21000051371752923 0.25000047061605735 0.10000015220117091 0.30999999888829144 0.10199913236874111 0.022999715346170929 0.0050000168620389848
251 0.21000030618472809 0.25000025816270716 0.10000011389270266 0.31000000124600918 0.10199948238020001 0.022999800400576097 0.0050000377330769279
261 0.2100000445095816 0.2499999902833088 0.1000000655900994 0.31000000421880708 0.10199992370466664 0.022999907644464797 0.0050000640490715734
271 0.21000008909654816 0.25000003592742104 0.10000007382040528 0.31000000371226893 0.10199984850715899 0.022999889371122236 0.0050000595650754173
281 0.21000000318197135 0.24999994797583083 0.10000005796143702 0.31000000468831079 0.10199999340515975 0.02299992458200726 0.005000068205283017
291 0.21000003070352388 0.24999997614991259 0.10000006304163929 0.31000000437564929 0.10199994698907894 0.022999913302684732 0.0050000654375114001

• Line 1: See Work time frame
• Lines 2-21: See Geographic data
• Lines 22-27: See Workers
• Lines 28-46: See Jobs
• Lines 47-55: See Weather
• Line 56: See Schedule
• Lines 57-86: Weather forecast data at beginning (t=1) (See Weather forecasts in Input 2).

Example 1:Actions + Initial schedule submission (t=1)

3
1 2 3
85 85 85 85 431 431 431 431 431 431
65 65 65 65 65 65 65 65 65 65
730 730 639 639 639 639 4 4 4 4
execute 85 135
move 12
move 98

• Line 1: Contestant is submitting schedules for 3 workers.
• Line 2: The applicable workers have ID=1,2,3.
• Line 3: This is the schedule for the first worker specified on Line 2 (ID=1), as follows:
  • At time 1 perform job with ID=85. Similarly at time 2 ID=85, at time 3 ID=85, at time 4 ID=85, at time 5 ID=431, at time 6 ID=431, at time 7 ID=431, at time 8 ID=431, at time 9 ID=431, and at time 10 ID=431.
• Line 4: This is the schedule for the first worker specified on Line 2 (ID=2), as follows:
  • At time 1 perform job with ID=65. Similarly at time 2 ID=65, at time 3 ID=65, at time 4 ID=65, at time 5 ID=65, at time 6 ID=65, at time 7 ID=65, at time 8 ID=65, at time 9 ID=65, and at time 10 ID=65.
• Line 5: This is the schedule for the first worker specified on Line 2 (ID=3), as follows:
  • At time 1 perform job with ID=730. Similarly at time 2 ID=730, at time 3 ID=639, at time 4 ID=639, at time 5 ID=639, at time 6 ID=639, at time 7 ID=4, at time 8 ID=4, at time 9 ID=4, and at time 10 ID=4.
• Line 6: Specify the action for the worker with ID=1 for the current time: Perform 135 tasks of the job with ID=85.
• Line 7: Specify the action for the worker with ID=2 for the current time: Move toward vertex 12.
• Line 8: Specify the action for the worker with ID=3 for the current time: Move toward vertex 98.

Example 2: Actions + no schedule changes

0

stay
move 87
execute 670 40

• Line 1: Contestant is submitting schedules for 0 workers (i.e., no schedule changes).
• Line 2: There are no applicable workers, so this line has 0 worker IDs (it is a blank line).
• (Missing lines: No worker schedules are output, so no lines are output.)
• Line 3: Specify the action for the worker with ID=1 for the current time: Do nothing.
• Line 4: Specify the action for the worker with ID=2 for the current time: Move toward vertex 87.
• Line 5: Specify the action for the worker with ID=3 for the current time: Perform 40 tasks of the job with ID=670.

Example 3: Actions + schedule changes (t=6)

2
2 3
65 65 65 65 223
639 4 4 91 91
execute 431 80
execute 65 40
move 9

• Line 1: Contestant is submitting schedule changes for 2 workers.
• Line 2: The applicable workers have ID=2,3.
• Line 3: This is the schedule for the first worker specified on Line 2 (ID=2), as follows:
  • At time 6 perform job with ID=65. Similarly at time 7 ID=65, at time 8 ID=65, at time 9 ID=65, and at time 10 ID=431.
• Line 4: This is the schedule for the second worker specified on Line 2 (ID=3), as follows:
  • At time 6 perform job with ID=639. Similarly at time 7 ID=4, at time 8 ID=4, at time 9 ID=91, and at time 10 ID=91.
• Line 5: Specify the action for the worker with ID=1 for the current time. Perform 80 tasks of the job with ID=431.
• Line 6: Specify the action for the worker with ID=2 for the current time. Perform 40 tasks of the job with ID=65.
• Line 7: Specify the action for the worker with ID=3 for the current time. Move toward vertex 9.

• Terminology

  • Here, we use the term partition for the operation of partitioning a rectangular area, [x_0,x_1]\times[y_0,y_1]\,\,(x_0<x_1,y_0<y_1), in half both vertically and horizontally, into four smaller rectangles.
  • Specifically, the operation divides the area [x_0,x_1]\times[y_0,y_1] into the following four pieces.
    • [x_0,(x_1+x_0)/2]\times[y_0,(y_0+y_1)/2]
    • [x_0,(x_1+x_0)/2]\times[(y_0+y_1)/2,y_1]
    • [(x_1+x_0)/2,x_1]\times[y_0,(y_0+y_1)/2]
    • [(x_1+x_0)/2,x_1]\times[(y_0+y_1)/2,y_1]
  • We also define a function, \text{Split}(R), which performs this operation (giving the above set of regions from a received rectangular region).

• Parameters

  • Rectangular region size:L>0
  • Maximum partition depth:d_\text{max} \in \mathbb{Z}_{\geq 0}
  • (Max) number of rectangles:M(integer 0 or greater, (4^{d_\text{max}+1}-1)/3 or less)
  • Distance minimum scale:s>0
  • Cut area ratio:C\in (0,1]

• Generation procedure 1 (generate graph)

  1. Prepare a set of rectangular regions, U=\{\}.
  2. Add rectangular region R=[0,L]\times[0,L] to U.
  3. If d_\text{max}=0, proceed to 8.
  4. Select a rectangle from U at random and call that rectangle r.
  5. If the area of r is L^2/4^{d_\text{max}}, return to 4.
  6. Add all elements from \text{Split}(R) to U.
     • If these elements are already in U, U does not change even if they are added.
  7. If |U| > Mis satisfied, proceed to 8. If not, return to 4.
  8. Create a weighted, non-directional graph, G=(V,E),W:E\rightarrow \mathbb{R}_{> 0}, from set A, the union of edges of all rectangles in U.
     • The set V of vertices in the graph consists of all points where line segments intersect in set A, the union of all edges.
     • The set of edges E in the graph consists of all pairs of vertices \{a,b\}, where a\neq b and it is possible to reach b from a on set A, the union of all edges, without passing through any other vertex.
     • The weight W is derived from the Euclidean distances between the points.
  9. This graph, G=(V,E) (with weight W), is used to generate the geographical data.

(Reference:Eisenstat, D., Random road networks: the quadtree model, Proceeding of the 8th Workshop on Analytic Algorithms and Combinatorics (ANALCO), pp.76-84, 2011 (DOI:https://doi.org/10.1137/1.9781611973013.9))

• Generation procedure 2 (generate elevations)
  1. Prepare a square region, R=[0,1024]\times[0,1024].
  2. Divide R by 128 in both x and y directions (creating 128\times128 square regions of size 8\times8).
  3. Randomly select 20 of these square regions from R and call the union of them A.
  4. Again, randomly select 20 of these square regions from R and call the union of them B.
  5. Solve the following partial differential equation discretized by the above dividing operation 2 to time t=100000 (in other words, compute u(100000,x,y)):

     \displaystyle \frac{\partial u}{\partial t}=\Delta u-b(x,y)u+a(x,y)

     The initial value at time t=0 is u(0,x,y)=u_0(x,y)\equiv 0, and we use Neumann boundary conditions. a(x,y) and b(x,y) are defined as follows:
     a(x,y)=\begin{cases} 1/8^2, & \text{if}\ (x,y) \in A, \\ 0, & \text{otherwise}, \end{cases}
     b(x,y)=\begin{cases} 1/8^2, & \text{if}\ (x,y) \in B, \\ 0, & \text{otherwise}. \end{cases}
     
  6. Normalize u(100000,x,y) to the range [0,1], and use it as the elevation, e(x,y).

• Generation procedure 3(cut the graph, distance scaling)

  1. Match the elevation data e(x,y) generated in procedure 2 to the size of the graph space, [0,L]\times[0,L]. In other words, define space-scaled elevation \tilde e(x,y), as \tilde e(x,y)= e(L\times x/1024,L\times y/1024).

  2. For function H(z)=\{(x,y) \in [0,L]\times[0,L]|\tilde e(x,y)>z\}, which returns the parts where \tilde e(x,y) is larger than real value z, call the largest value of z for which the area of H(z) is C\times L^2 or greater, h.

  3. For the set of graph edges E generated in generation procedure 1, delete all edges from E where the two vertices on the both ends are below h.
  4. Let the graph G'=(V',E') be the largest connected component of graph G=(V,E).
  5. Define weight W':E' \rightarrow \mathbb{R}_{> 0}: as follows:W'(e)= s\times W(e)/\min_{e' \in E'}W(e')
  6. Use the graph G'=(V',E') (with weight W') as the geographical data.

• Parameters
  • The desired stationary distribution for the transition probability matrix:\bm{s}^\text{sta}=(s^\text{sta}_1,s^\text{sta}_2,\cdots,s^\text{sta}_{N^\text{weather}})
  • Bandwidth of the matrix (as a band matrix):d \geq 1
  • Small value for convergence test:\epsilon > 0
  • Maximum loop iterations:M\geq 1
  • Intensity of diagonal component:q > 0

~

1. The N^\text{weather}\times N^\text{weather} matrix A is determined as follows:

   Set the element a_{i,j} at row i and column j, to a_{i,j}=\begin{cases} \exp(-q|i-j|^2), & \text{if}\ |i-j|\leq d,\\ 0, & \text{otherwise.} \end{cases}

2. Normalize each row of A so that the sum is 1.
3. Initialize the loop counter:l=0
4. l\leftarrow l + 1
5. If l>M, use A as the transition probability matrix and exit.
6. Compute the stationary distribution \bm{s} of A.
7. Set matrix P as follows.:

   Set element p_{i,j} at row i and column j to p_{i,j}=\begin{cases} N^\text{weather}||\bm{s}^\text{sta}-\bm{s}||_\infty\max\{\epsilon,a_{i,j}\}\text{rand}(-1,1), & \text{if}\ |i-j|\leq d,\\ 0, & \text{otherwise.} \end{cases}

   Here, ||\cdot||_\infty is the maximum norm, representing the maximum absolute value of the elements. \text{rand}(a,b) represents a random number from the uniform distribution on [a,b]. Random numbers are generated when each element is computed.
8. Let the matrix A'=A+P
9. Perform the following update on all rows of A'. For the i-th row:
   1. Compute m_i, the value of the smallest element.
   2. If m_i < 0, add -m_i to the value of all elements in columns j which satisfy |i-j|\leq d.
   3. Normalize the row so that the sum equals 1.
10. For each row in A', if the diagonal component is not the unique maximum component, return to 4.
11. Compute \bm{s}', the stationary distribution of A'.
12. If ||\bm{s}^\text{sta}-\bm{s}||_\infty > ||\bm{s}^\text{sta}-\bm{s'}||_\infty, update A by substituting A with A'.
13. If the both conditions, "||\bm{s}^\text{sta}-\bm{s'}||_\infty < \epsilon N^\text{weather}" and "Every element a_{i,j} of A at row i and column j which satisfies |i-j|\leq d, is positive.", are satisified, use A as the transition probability matrix and exit. If this is not the case, return to 4.

• Parameters
  • Length of section with positive reward:L\geq 1
  • Length for partitioning the interval:l\geq 1
  • Reward standard value:s > 0
  • Standard deviation used when generating control point value:\sigma' > 0
  • Reward upper limit:M > 0
  • Reward lower limit:m > 0

~

1. Let the reward start time be b=\text{randint}(1,T_\text{max}-L), the reward end time be e=b+L, and the number of segments be d=\text{round}(L/l). Here, \text{randint}(m,n) is a function that uniformly selects a random integer between m and n inclusive, and \text{round}(x) is a function that returns the value x rounded to the nearest integer.
2. Generate d+1 independent random values which follow a log-normal distribution with \mu=0 and \sigma=\sigma', and let them be \{c_i\}_{i=1}^{d+1}.
3. Define \{v_i\}_{i=1}^{d+1} by v_i=\prod_{j=1}^{i}c_j.
4. Let B=s\sqrt{(d+1)/\sum_{i=1}^{d+1}v_i^2}, and define \{r_i\}_{i=1}^{d+1} by r_i=\text{round}(Bv_i).
5. If there exists i such that r_i > M or r_i < m, return to 2.
6. Let t_i=\text{round}(b+(i-1)L/d), and use the list of time and reward value pairs ((b-1,0),(t_1,r_1),(t_2,r_2),\cdots,(t_{d+1},r_{d+1}),(e+1,0)) as the list of control points.