-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathOneMachDPCritPath.cpp
More file actions
250 lines (234 loc) · 7.59 KB
/
OneMachDPCritPath.cpp
File metadata and controls
250 lines (234 loc) · 7.59 KB
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include "OneMachineDP.h"
void OneMachDPCritPath::initialize()
{
if (mOneMachDPData != nullptr) {
mJsonFile = mOneMachDPData->mJsonFile;
}
mPosInPathByJob.resize(mOneMachDPData->numJobs);
mIndInPathByPos.resize(mOneMachDPData->numJobs);
mIndexedJob.resize(mOneMachDPData->numJobs);
}
void OneMachDPCritPath::main(OneMachDPNode* node)
{
mCurNode = node;
mCurFeaSol = mCurNode->mFeaSol;
mLgstPathesByJob.resize(mOneMachDPData->numJobs);
mMaxLgthToJob.resize(mOneMachDPData->numJobs, -1);
mCanBeInCritPath.resize(mOneMachDPData->numJobs, 0);
mAllCritPath.clear();
fillPosAndIndex();
auto iter = mCurNode->mSolPath.begin();
auto end = mCurNode->mSolPath.end();
while (iter != end) {
findAllLgestPathToJob(*iter);
iter++;
}
findAllCritPath();
//filterCritPath();
findValidCritPath();
mLgstPathesByJob.clear();
mMaxLgthToJob.clear();
mCanBeInCritPath.clear();
}
void OneMachDPCritPath::fillPosAndIndex()
{
auto iter = mCurNode->mSolPath.begin();
auto end = mCurNode->mSolPath.end();
int count = 0;
while (iter != end) {
mPosInPathByJob[(*iter)->jobIndex] = count;
mIndInPathByPos[count] = (*iter)->jobIndex;
mIndexedJob[(*iter)->jobIndex] = *iter;
iter++;
count++;
}
}
int OneMachDPCritPath::findAllLgestPathToJob(JobStep* curJob)
{
int maxPathLgth;
int curPathLgth;
int curIndex = curJob->jobIndex;
bool hasLastStepAsPred = false;
vector<int> maxLgthIndices;
// If current jobstep has already calculated, just return
if (mMaxLgthToJob[curIndex] != -1) {
return mMaxLgthToJob[curIndex];
}
// If current jobstep is the fisrt, then only one path is possible
if (mPosInPathByJob[curIndex] == 0) {
mMaxLgthToJob[curIndex] = curJob->head;
list<JobStep*> curPath;
curPath.push_back(curJob);
mLgstPathesByJob[curIndex].push_back(curPath);
//mLgstPathesByJob[curIndex].push_back(list<JobStep*>());
//mLgstPathesByJob[curIndex].back().push_back(curJob);
// If current job step can be used as the last step in critical path, record that
if (curJob->head + curJob->body + curJob->tail == mCurFeaSol)
mCanBeInCritPath[curIndex] = 1;
return mMaxLgthToJob[curIndex];
}
// Otherwise, best can come from 1) Previous jobstep, 2) Anyone of the DPC predecessors or 3) current node itself
int curPos = mPosInPathByJob[curIndex];
int prevIndex = mIndInPathByPos[curPos - 1];
// Set max to be from previous jobstep
maxPathLgth = findAllLgestPathToJob(mIndexedJob[prevIndex]);
maxPathLgth += (mIndexedJob[prevIndex]->body + mOneMachDPData->getDelay(prevIndex, curIndex));
// Check if job prevIndex can be last in critical path
//if (mCanBeInCritPath[prevIndex] == 0)
maxLgthIndices.push_back(prevIndex);
// If predecessor exists, check DPCs
if (!mCurNode->mAllPreds[curIndex].empty()) {
auto iter = mCurNode->mAllPreds[curIndex].begin();
auto end = mCurNode->mAllPreds[curIndex].end();
JobStep* predStep;
while (iter != end) {
// Only DPCs matter
if ((*iter)->delay != 0) {
predStep = (*iter)->from;
curPathLgth = findAllLgestPathToJob(predStep);
curPathLgth += (predStep->body + mOneMachDPData->getDelay(predStep->jobIndex, curIndex));
if (curPathLgth > maxPathLgth) {
maxLgthIndices.clear();
maxPathLgth = curPathLgth;
}
int predStepIndex = predStep->jobIndex;
if (predStepIndex == prevIndex) {
iter++;
continue;
}
//if (curPathLgth >= maxPathLgth && mCanBeInCritPath[predStepIndex] == 0)
if (curPathLgth >= maxPathLgth) {
maxLgthIndices.push_back(predStepIndex);
}
} else {
break;
}
iter++;
}
}
// Last, check current head
if (maxPathLgth < curJob->head) {
// Longest path is starting from current jobstep itself
maxPathLgth = curJob->head;
mMaxLgthToJob[curIndex] = maxPathLgth;
if (curJob->head + curJob->body + curJob->tail == mCurFeaSol)
mCanBeInCritPath[curIndex] = 1;
mLgstPathesByJob[curIndex].push_back(list<JobStep*>());
mLgstPathesByJob[curIndex].back().push_back(curJob);
return mMaxLgthToJob[curIndex];
}
mMaxLgthToJob[curIndex] = maxPathLgth;
if (maxLgthIndices.empty())
//mCanBeInCritPath[curIndex] = -1;
mCanBeInCritPath[curIndex] = 0;
else {
for (int maxLgthIndex : maxLgthIndices) {
if (curIndex == maxLgthIndex) continue;
auto pathIter = mLgstPathesByJob[maxLgthIndex].begin();
auto pathEnd = mLgstPathesByJob[maxLgthIndex].end();
for (; pathIter != pathEnd; pathIter++) {
list<JobStep*> curPath = (*pathIter);
curPath.push_back(curJob);
mLgstPathesByJob[curIndex].push_back(curPath);
}
}
if (maxPathLgth + curJob->body + curJob->tail == mCurFeaSol)
mCanBeInCritPath[curIndex] = 1;
}
return mMaxLgthToJob[curIndex];
}
void OneMachDPCritPath::findAllCritPath()
{
int jobIndex;
for (int i = 0; i < mOneMachDPData->numJobs; i++) {
jobIndex = mIndInPathByPos[i];
// If current job is the last job in critical path, then add all its longest pathes to critical path list
if (mCanBeInCritPath[jobIndex] == 1) {
auto iter = mLgstPathesByJob[jobIndex].begin();
auto end = mLgstPathesByJob[jobIndex].end();
while (iter != end) {
mAllCritPath.push_back((*iter));
//(*iter).clear();
iter++;
}
}
//mLgstPathesByJob[jobIndex].clear();
}
}
/************************************************************************************************************
* Allow each jobstep to be first in critical path once *
************************************************************************************************************/
void OneMachDPCritPath::filterCritPath()
{
int curTopIndex, curPathLgth;
auto pathIter = mAllCritPath.begin();
vector<int> canBeTopCritPath;
vector<list<JobStep*>> candidatPathes;
canBeTopCritPath.resize(mOneMachDPData->numJobs, 0);
candidatPathes.resize(mOneMachDPData->numJobs);
for (auto path : mAllCritPath) {
curTopIndex = path.front()->jobIndex;
curPathLgth = path.size();
// take the first path with curTopIndex as first job
if (canBeTopCritPath[curTopIndex] == 0) {
canBeTopCritPath[curTopIndex] = curPathLgth;
candidatPathes[curTopIndex] = path;
}
}
mAllCritPath.clear();
for (int i = 0; i < mOneMachDPData->numJobs; i++) {
if (canBeTopCritPath[i] > 0)
mAllCritPath.push_back(candidatPathes[i]);
}
}
/************************************************************************************************************
* Remove critical pathes that can be extended to preceding jobs *
************************************************************************************************************/
void OneMachDPCritPath::findValidCritPath()
{
int curPos, curIndex;
JobStep* curStep;
JobStep* preStep;
auto pathIter = mAllCritPath.begin();
auto pathEnd = mAllCritPath.end();
while (pathIter != pathEnd) {
curStep = (*pathIter).front();
curIndex = curStep->jobIndex;
curPos = mPosInPathByJob[curIndex];
if (curPos == 0) {
pathIter++;
continue;
}
preStep = mIndexedJob[mIndInPathByPos[curPos - 1]];
// If there is a gap before the first job of critical path
if (mMaxLgthToJob[curIndex] - mMaxLgthToJob[preStep->jobIndex] - preStep->body > 0) {
bool byDPC = false;
auto iter = mCurNode->mAllPreds[curIndex].begin();
auto end = mCurNode->mAllPreds[curIndex].end();
while (iter != end) {
if ((*iter)->delay == 0) {
iter++;
continue;
}
if (mMaxLgthToJob[curIndex] - mMaxLgthToJob[(*iter)->from->jobIndex] - (*iter)->delay == 0) {
byDPC = true;
break;
}
iter++;
}
if (byDPC) {
mAllCritPath.erase(pathIter);
continue;
}
} else {
// if no gap, we simply ignore such critical path
mAllCritPath.erase(pathIter);
continue;
}
pathIter++;
}
}
void OneMachDPCritPath::clearPathes()
{
mAllCritPath.clear();
}