This repository has been archived by the owner on Aug 23, 2023. It is now read-only.
/
AssemblyLineScheduling.cs
131 lines (108 loc) · 4.8 KB
/
AssemblyLineScheduling.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CS.Problems.DynamicProgramming
{
/// <summary>
/// problem details below
/// http://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/
/// </summary>
public class AssemblyLineScheduling
{
public static int GetMinTime(int[][] stationTime, int[][] crossingTime,
int[] entryTime, int[] exitTime)
{
var stations = stationTime[0].Length;
var cache = new Dictionary<string, int>();
return Math.Min(MinTimeStationA(stationTime[0], stationTime[1],
crossingTime[0], crossingTime[1],
entryTime[0], entryTime[1],
exitTime[0], exitTime[1],
stations - 1, stations, cache),
MinTimeStationB(stationTime[0], stationTime[1],
crossingTime[0], crossingTime[1],
entryTime[0], entryTime[1],
exitTime[0], exitTime[1]
, stations - 1, stations, cache)
);
}
private static int MinTimeStationA(int[] stationATime, int[] stationBTime,
int[] AB_crossingTime, int[] BA_crossingTime,
int entryTimeA, int exitTimeA,
int entryTimeB, int exitTimeB,
int currentStation, int totalStations, Dictionary<string, int> cache)
{
//first station
if (currentStation == 0)
{
return entryTimeA + stationATime[0];
}
var cacheKey = $"A-{currentStation}";
if (cache.ContainsKey(cacheKey))
{
return cache[cacheKey];
}
var prevMinA = MinTimeStationA(stationATime, stationBTime,
AB_crossingTime, BA_crossingTime,
entryTimeA, entryTimeB,
exitTimeA, exitTimeB,
currentStation - 1, totalStations, cache)
+ stationATime[currentStation];
var prevMinB = MinTimeStationB(stationATime, stationBTime,
AB_crossingTime, BA_crossingTime,
entryTimeA, entryTimeB,
exitTimeA, exitTimeB,
currentStation - 1, totalStations, cache)
+ BA_crossingTime[currentStation] + stationATime[currentStation];
//last station
if (currentStation == totalStations - 1)
{
prevMinA += exitTimeA;
prevMinB += exitTimeB;
}
var min = Math.Min(prevMinA, prevMinB);
cache.Add(cacheKey, min);
return min;
}
private static int MinTimeStationB(int[] stationATime, int[] stationBTime,
int[] AB_crossingTime, int[] BA_crossingTime,
int entryTimeA, int exitTimeA,
int entryTimeB, int exitTimeB,
int currentStation, int totalStations, Dictionary<string, int> cache)
{
//first station
if (currentStation == 0)
{
return entryTimeB + stationBTime[0];
}
var cacheKey = $"B-{currentStation}";
if (cache.ContainsKey(cacheKey))
{
return cache[cacheKey];
}
var prevMinB = MinTimeStationB(stationATime, stationBTime,
AB_crossingTime, BA_crossingTime,
entryTimeA, entryTimeB,
exitTimeA, exitTimeB,
currentStation - 1, totalStations, cache)
+ stationBTime[currentStation];
var prevMinA = MinTimeStationA(stationATime, stationBTime,
AB_crossingTime, BA_crossingTime,
entryTimeA, entryTimeB,
exitTimeA, exitTimeB,
currentStation - 1, totalStations, cache)
+ AB_crossingTime[currentStation] + stationBTime[currentStation];
//last station
if (currentStation == totalStations - 1)
{
prevMinA += exitTimeA;
prevMinB += exitTimeB;
}
var min = Math.Min(prevMinA, prevMinB);
cache.Add(cacheKey, min);
return min;
}
}
}