C语言实现工件排序和分配算法 - 设备重量和体积约束优化

//定义一个工件结构体 typedef struct{ int id; //工件序号 float weight; //工件重量 float volume; //工件体积 }Workpiece;

//定义一个扇区结构体 typedef struct{ Workpiece wp[4]; //扇区内的4个工件 float totalWeight; //扇区内4个工件的总重量 }Sector;

//冒泡排序，按照重量从大到小排序 void bubbleSortByWeight(Workpiece arr[], int n){ int i, j; Workpiece temp; for(i=0; i<n-1; i++){ for(j=0; j<n-1-i; j++){ if(arr[j].weight < arr[j+1].weight){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }

//冒泡排序，按照体积从大到小排序 void bubbleSortByVolume(Workpiece arr[], int n){ int i, j; Workpiece temp; for(i=0; i<n-1; i++){ for(j=0; j<n-1-i; j++){ if(arr[j].volume < arr[j+1].volume){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }

//计算扇区内4个工件的总重量 float calculateTotalWeight(Workpiece wp[]){ float total = 0; int i; for(i=0; i<4; i++){ total += wp[i].weight; } return total; }

//计算两个扇区的重量差 float calculateWeightDifference(Sector s1, Sector s2){ float total1 = s1.totalWeight; float total2 = s2.totalWeight; float diff = total1 - total2; if(diff < 0){ diff = -diff; } return diff; }

//将两个扇区内的工件进行交换 void swapWorkpieces(Sector *s1, int index1, Sector *s2, int index2){ Workpiece temp = s1->wp[index1]; s1->wp[index1] = s2->wp[index2]; s2->wp[index2] = temp; }

//计算工件体积差 float calculateVolumeDifference(Workpiece wp1, Workpiece wp2){ float diff = wp1.volume - wp2.volume; if(diff < 0){ diff = -diff; } return diff; }

//找到扇区内体积最大的工件 Workpiece* findMaxVolumeWorkpiece(Sector *s){ Workpiece *maxWp = &s->wp[0]; int i; for(i=1; i<4; i++){ if(s->wp[i].volume > maxWp->volume){ maxWp = &s->wp[i]; } } return maxWp; }

//找到扇区内体积最小的工件 Workpiece* findMinVolumeWorkpiece(Sector *s){ Workpiece *minWp = &s->wp[0]; int i; for(i=1; i<4; i++){ if(s->wp[i].volume < minWp->volume){ minWp = &s->wp[i]; } } return minWp; }

int main(){ //定义设备 Sector upper[5]; //上部分5个扇区 Sector lower[5]; //下部分5个扇区

//定义工件数组
Workpiece wp[40] = {
    {1, 348, 101.5},
    {2, 352, 102},
    {3, 347, 105},
    {4, 349, 105.5},
    {5, 347.5, 106},
    {6, 347, 104},
    {7, 330, 94},
    {8, 329, 98},
    {9, 329, 100.5},
    {10, 327.5, 98.5},
    {11, 329, 98},
    {12, 331.5, 99},
    {13, 348.5, 104.5},
    {14, 347, 105},
    {15, 346.5, 107.5},
    {16, 348, 104.5},
    {17, 347.5, 104},
    {18, 348, 104.5},
    {19, 333, 97},
    {20, 330, 98},
    {21, 332.5, 99},
    {22, 331.5, 98},
    {23, 331.5, 96.5},
    {24, 332, 94},
    {25, 332.5, 94.5},
    {26, 331, 96},
    {27, 330, 97},
    {28, 340, 97.5},
    {29, 350, 98},
    {30, 351, 96.5},
    {31, 332, 98},
    {32, 331.5, 100},
    {33, 347.5, 104},
    {34, 332, 96},
    {35, 329, 98},
    {36, 331, 99},
    {37, 348, 103.5},
    {38, 347, 105},
    {39, 345.5, 107},
    {40, 348, 104.5}
};

//将所有工件按照重量从大到小排序
bubbleSortByWeight(wp, 40);

//将工件依次放入每个扇区中
int i, j;
for(i=0; i<5; i++){
    for(j=0; j<4; j++){
        upper[i].wp[j] = wp[i*4+j];
    }
    //计算扇区内4个工件的总重量
    upper[i].totalWeight = calculateTotalWeight(upper[i].wp);
    //将扇区内的工件按照体积从大到小排序
    bubbleSortByVolume(upper[i].wp, 4);
}
for(i=0; i<5; i++){
    for(j=0; j<4; j++){
        lower[i].wp[j] = wp[20+i*4+j];
    }
    //计算扇区内4个工件的总重量
    lower[i].totalWeight = calculateTotalWeight(lower[i].wp);
    //将扇区内的工件按照体积从大到小排序
    bubbleSortByVolume(lower[i].wp, 4);
}

//处理重量差要求
int k;
for(k=0; k<10; k++){
    for(i=0; i<5; i++){
        Sector *currentSector = &upper[i];
        Sector *neighbourSector = NULL;
        float diff = 0;
        //与上方扇区比较
        if(i > 0){
            neighbourSector = &upper[i-1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 0, neighbourSector, 3);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与下方扇区比较
        if(i < 4){
            neighbourSector = &upper[i+1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 3, neighbourSector, 0);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与左侧扇区比较
        if(i > 0){
            neighbourSector = &lower[i-1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 0, neighbourSector, 3);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与右侧扇区比较
        if(i < 4){
            neighbourSector = &lower[i+1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 3, neighbourSector, 0);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
    }
    for(i=0; i<5; i++){
        Sector *currentSector = &lower[i];
        Sector *neighbourSector = NULL;
        float diff = 0;
        //与上方扇区比较
        if(i > 0){
            neighbourSector = &upper[i-1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 0, neighbourSector, 3);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与下方扇区比较
        if(i < 4){
            neighbourSector = &upper[i+1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 3, neighbourSector, 0);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与左侧扇区比较
        if(i > 0){
            neighbourSector = &lower[i-1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 0, neighbourSector, 3);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
        //与右侧扇区比较
        if(i < 4){
            neighbourSector = &lower[i+1];
            diff = calculateWeightDifference(*currentSector, *neighbourSector);
            while(diff > 4){
                swapWorkpieces(currentSector, 3, neighbourSector, 0);
                currentSector->totalWeight = calculateTotalWeight(currentSector->wp);
                neighbourSector->totalWeight = calculateTotalWeight(neighbourSector->wp);
                diff = calculateWeightDifference(*currentSector, *neighbourSector);
            }
        }
    }
}

//处理体积差要求
for(k=0; k<10; k++){
    for(i=0; i<5; i++){
        Sector *s = &upper[i];
        Workpiece *maxWp = NULL;
        Workpiece *minWp = NULL;
        float diff = 0;
        //计算每个工件与其左右两个工件的体积差
        for(j=1; j<=2; j++){
            maxWp = findMaxVolumeWorkpiece(s);
            minWp = findMinVolumeWorkpiece(s);
            diff = calculateVolumeDifference(*maxWp, *(maxWp-j));
            if(diff < 3.5){
                break;
            }
            diff = calculateVolumeDifference(*minWp, *(minWp+j-2));
            if(diff < 3.5){
                break;
            }
        }
        //如果体积差大于3.5，则进行交换
        if(diff >= 3.5){
            if(maxWp->volume - (maxWp-j)->volume > (minWp+j-2)->volume - minWp->volume){
                swapWorkpieces(s, maxWp-s->wp, s, maxWp-j-s->wp);
            }
            else{
                swapWorkpieces(s, minWp-s->wp, s, minWp+j-2-s->wp);
            }
        }
    }
    for(i=0; i<5; i++){
        Sector *s = &lower[i];
        Workpiece *maxWp = NULL;
        Workpiece *minWp = NULL;
        float diff = 0;
        //计算每个工件与其左右两个工件的体积差
        for(j=1; j<=2; j++){
            maxWp = findMaxVolumeWorkpiece(s);
            minWp = findMinVolumeWorkpiece(s);
            diff = calculateVolumeDifference(*maxWp, *(maxWp-j));
            if(diff < 3.5){
                break;
            }
            diff = calculateVolumeDifference(*minWp, *(minWp+j-2));
            if(diff < 3.5){
                break;
            }
        }
        //如果体积差大于3.5，则进行交换
        if(diff >= 3.5){
            if(maxWp->volume - (maxWp-j)->volume > (minWp+j-2)->volume - minWp->volume){
                swapWorkpieces(s, maxWp-s->wp, s, maxWp-j-s->wp);
            }
            else{
                swapWorkpieces(s, minWp-s->wp, s, minWp+j-2-s->wp);
            }
        }
    }
}

//按工件序号输出每层每个扇区的4个工件组合
for(i=0; i<5; i++){
    printf("Upper Sector %d: [%d, %d, %d, %d]

", i+1, upper[i].wp[0].id, upper[i].wp[1].id, upper[i].wp[2].id, upper[i].wp[3].id); } for(i=0; i<5; i++){ printf("Lower Sector %d: [%d, %d, %d, %d] ", i+1, lower[i].wp[0].id, lower[i].wp[1].id, lower[i].wp[2].id, lower[i].wp[3].id); } return 0;