流水线的工程调度问题

流水作业调度问题

n个产品{1，2，…，n}要在由3台机器M1和M2，M3组成的流水线上完成加工。每个产品加工的顺序都是先在M1上加工 然后在M2上再M3加工。M1和M2，M3加工产品i所需的时间分别为ai 和bi,ci。流水作业调度问题要求确定这n个产品的最优加工顺序， 使得从第一个产品在机器M1上开始加工，到最后一个产品在机器M3上加工完成所需的时间最少。并输出时间

网上有M1和M2的源码，我想要达到有三台机器的这个源码，但是自己能力不够修改不了，希望看见之后能够把源码修改完毕后发到这里，用c或c++来写

你的源码发我，我给你改造

#include<bits/stdc++.h>
using namespace std;
const int N = 5;

class Jobtype
{
    public:
    int job_time,index;//job_time为机器所用时间，index为作业序号
    int job_machine;//job_machine为1表示M1,2表示M2,3表示M3,
    inline bool operator <(const Jobtype &a) const //重载 <=
    {
        return(job_time<a.job_time);
    }
};

int FlowShop(int n,int a[],int b[],int c[],int d[]);
int main()
{
    int a[] = {2,4,3,6,1};
    int b[] = {5,2,3,1,7};
    int c[] = {7,3,1,5,2};
    int d[N];
    int minTime =  FlowShop(N,a,b,c,d);
     
    cout<<"作业在机器1上的运行时间为："<<endl;
    for(int i=0; i<N; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<"作业在机器2上的运行时间为："<<endl;
    for(int i=0; i<N; i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
    cout<<"作业在机器3上的运行时间为："<<endl;
    for(int i=0; i<N; i++)
    {
        cout<<c[i]<<" ";
    }
    cout<<endl;
     
    cout<<"完成作业的最短时间为："<<minTime<<endl;
    cout<<"编号从0开始，作业调度的顺序为："<<endl;
    for(int i=0; i<N; i++)
    {
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}

int FlowShop(int n,int a[],int b[],int c[],int d[])
{
    Jobtype *job = new Jobtype[n];
    for(int i=0; i<n; i++)
    {
        job[i].job_time = a[i]>b[i]?(b[i]>c[i]?c[i]:b[i]):(a[i]>c[i]?c[i]:a[i]);//按Johnson法则分别取对应的b[i]或a[i]值作为关键字
        //找作业在两台机器上处理时间小的那个作业
        job[i].job_machine = a[i]>b[i]?(b[i]>c[i]?3:2):(a[i]>c[i]?3:1);//给符合条件a[i]<b[i]的放入到N1子集标记为true
        job[i].index = i;
    }
    sort(job,job+n);//对数组job按关键字升序进行排序 快排
 
    int j = 0,k = n-1;
 
    for(int i=0; i<n; i++)
    {
        if(job[i].job_machine == 1)//N1集合，ai<=bi
        {
            d[j++] = job[i].index;//将排过序的数组job，取其中作业序号属于N1的从前面进入
        }
        else if (job[i].job_machine == 3)//N2集合，ai>bi
        {
            d[k--] = job[i].index;//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序
        }
    }
    int tmp_index = j;
    for(int i=0; i<n; i++){
        if(job[i].job_machine == 2){
            d[tmp_index++] = job[i].index;
        }
    }
 
    int time1 = a[d[0]];//第一个作业在M1上的处理时间
    int time2 = time1+b[d[0]];//第一个作业处理完所需时间
    int time3 = time2+c[d[0]];//第一个作业处理完所需时间
    for(int i=1; i<n; i++)
    {
        time1 += a[c[i]];//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完
        time2 = time1<time2?time2+b[d[i]]:time1+b[d[i]];//计算最优加工时间
        time3 = time2<time3?time3+c[d[i]]:time2+c[d[i]];//计算最优加工时间
    }
     
    delete job;
    return time3;
}

改造完成

img


也不知道这个算法是否正确哈，算法的问题我没法给你意见

#include<bits/stdc++.h>
using namespace std;
const int N = 5;

class Jobtype
{
public:
int key,index;//key为机器所用时间，index为作业序号
bool job;//job为ture表示M1,false表示M2
inline bool operator <(const Jobtype &a) const //重载 <=
{
return(key<a.key);
}
};

int FlowShop(int n,int a[],int b[],int c[]);

int main()
{
int a[] = {2,4,3,6,1};
int b[] = {5,2,3,1,7};
int c[N];

int minTime =  FlowShop(N,a,b,c);

cout<<"作业在机器1上的运行时间为："<<endl;
for(int i=0; i<N; i++)
{
    cout<<a[i]<<" ";
}
cout<<endl;
cout<<"作业在机器2上的运行时间为："<<endl;
for(int i=0; i<N; i++)
{
    cout<<b[i]<<" ";
}
cout<<endl;

cout<<"完成作业的最短时间为："<<minTime<<endl;
cout<<"编号从0开始，作业调度的顺序为："<<endl;
for(int i=0; i<N; i++)
{
    cout<<c[i]<<" ";
}
cout<<endl;
return 0;

}

int FlowShop(int n,int a[],int b[],int c[])
{
Jobtype *d = new Jobtype[n];
for(int i=0; i<n; i++)
{
d[i].key = a[i]>b[i]?b[i]:a[i];//按Johnson法则分别取对应的b[i]或a[i]值作为关键字
//找作业在两台机器上处理时间小的那个作业
d[i].job = a[i]<=b[i];//给符合条件a[i]<b[i]的放入到N1子集标记为true
d[i].index = i;
}

sort(d,d+n);//对数组d按关键字升序进行排序 快排

int j = 0,k = n-1;

for(int i=0; i<n; i++)
{
    if(d[i].job)//N1集合，ai<=bi
    {
        c[j++] = d[i].index;//将排过序的数组d，取其中作业序号属于N1的从前面进入
    }
    else//N2集合，ai>bi
    {
        c[k--] = d[i].index;//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序
    }
}

j = a[c[0]];//第一个作业在M1上的处理时间
k = j+b[c[0]];//第一个作业处理完所需时间
for(int i=1; i<n; i++)
{
    j += a[c[i]];//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完
    k = j<k?k+b[c[i]]:j+b[c[i]];//计算最优加工时间
}

delete d;
return k;

}

源码