当前位置：首页 > news >正文

加工生产调度（Johnson算法）

news 2025/5/23 10:15:01

问题：

场景：工厂有n个产品，必须按顺序在A车间和B车间加工（先A后B）

目标：安排产品加工顺序，使得从开始到所有产品加工完成的总时间最短

关键限制：B车间必须等A完成后才能开始加工同一产品

上面是一个例子

它是让A的最早加工产品地加工时间尽可能地少，也就相当于降序排列。

又让B的最早加工产品的加工时间尽可能地多，也就是相当于升序排序。

但是，它不仅仅是这样做的

它是把上面地数据分成了两组，A<B放一组，A>B的放一组

对于A<B这一组按照A进行降序排列

对于A>B这一组按照B进行升序排列

至于为什么这样可以达到调度最优的问题我还是没有理解。

	sort(arr.begin(),arr.end(),[](const vector<int>&a,const vector<int>&b){bool a_group1 = (a[0]<=a[1]); // a是否属于group1bool b_group1 = (b[0]<=b[1]); // b是否属于group1if(a_group1&&b_group1){return a[0]<b[0]; // a,b都在group1，Group1按A_i降序排列}else if(!a_group1&&!b_group1){return a[1]>b[1]; // a,b都不在group1，Group2按B_i升序排列}else{return a_group1; // Group1优先于Group2}});

总代码：

# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;int main()
{int n;cin>>n;vector<vector<int>> arr(n,vector<int>(2));for(int i=0;i<n;i++){cin>>arr[i][0];}for(int i=0;i<n;i++){cin>>arr[i][1];}sort(arr.begin(),arr.end(),[](const vector<int>&a,const vector<int>&b){bool a_group1 = (a[0]<=a[1]); // a是否属于group1bool b_group1 = (b[0]<=b[1]); // b是否属于group1if(a_group1&&b_group1){return a[0]<b[0]; // a,b都在group1，Group1按A_i降序排列}else if(!a_group1&&!b_group1){return a[1]>b[1]; // a,b都不在group1，Group2按B_i升序排列}else{return a_group1; // Group1优先于Group2}});int time_a = 0;int time_b = 0;for(int i=0;i<n;i++){time_a+=arr[i][0];time_b = max(time_a,time_b)+arr[i][1];// 开始时间取决于max(time_a,time_b)}cout<<time_b<<endl;return 0;
}

题目：