Article directory
- 1. Problem Overview
-
- 1.1 Idea analysis
- 1.2 Example analysis
- 2. Code writing
1. Problem Overview
1.1 Idea analysis
?1. Have
n
n
n independent jobs
1
,
2
,
…
,
n
{1, 2, …, n}
1,2,…,n, given by
m
m
m identical machines
M
1
,
M
2
,
…
,
M
m
{M_1, M_2, …, M_m}
M1?,M2?,…,Mm? for processing and operation
i
i
The processing time required for i is
t
i
(
1
≤
i
≤
n
)
t_i(1≤i≤n)
ti?(1≤i≤n), each job can be processed on any machine, but it cannot be interrupted or split. The multi-machine scheduling problem requires a job scheduling plan so that the given
n
n
n jobs are run in the shortest possible time by
m
m
m machines are processed.
?2. Solution: (1) If
n
<
m
n
m
n>m
If n>m, use greedy algorithm to solve.
?3. The greedy strategy of the greedy algorithm to solve multi-machine scheduling problems is the job with the longest processing time first, that is, the job with the longest processing time is assigned to the first idle machine, so that the processing time can be guaranteed Longer jobs are processed first, resulting in the shortest possible processing time overall.
1.2 Example Analysis
?set up
7
7
7 independent assignments
1
,
2
,
3
,
4
,
5
,
6
,
7
{1, 2, 3, 4, 5, 6, 7}
1,2,3,4,5,6,7 by
3
3
3 machines
M
1
,
M
2
,
M
3
{M1, M2, M3}
M1, M2, M3 processing, the processing time required for each operation is respectively
2
,
14
,
4
,
16
,
6
,
5
,
3
{2, 14, 4, 16, 6, 5, 3}
2,14,4,16,6,5,3. The job schedule generated by the greedy algorithm is shown in the figure below. The required processing time is 17.
2. Code writing
#include<bits/stdc + + .h>
using namespace std;
bool compare(int a,int b)
{<!-- -->
return a>b;
}
int main(){<!-- -->
int n,m; //The number of jobs is n, the number of machines is m
\t
cout<<"Please enter the number of jobs and machines:"<<endl;
cin>>n>>m;
\t
vector<int> time(n);
//vector<vector<int> > machine(m); //Understood as an m×1 two-dimensional array
vector<int> sumTime(m,0); //0 means the initialization value is 0
\t
cout<<"Please enter the processing time of each job:"<<endl;
for(int i=0;i<n;i + + )
{<!-- -->
cin>>time[i];
}
sort(time.begin(),time.end(),compare); //Sort time from large to small.
\t
for(int i=0;i<n;i + + )
{<!-- -->
int select=0;
for(int j=0;j<m;j + + )
{<!-- -->
if(sumTime[j]<sumTime[select])
{<!-- -->
select=j;
}
}
\t\t
//machine[select].push_back(time[i]);
sumTime[select]=sumTime[select] + time[i];
}
\t
int maxTime=sumTime[0];
for(int j=0;j<m;j + + )
{<!-- -->
if(sumTime[j]>maxTime)
{<!-- -->
maxTime=sumTime[j];
}
}
for(int j=0;j<m;j + + )
{<!-- -->
cout<<"The total processing time required by the "<<j + 1<<" machine is: "<<sumTime[j]<<endl;
}
\t
cout<<"Total time required to process all operations: "<<maxTime;
return 0;
}
