精华内容
下载资源
问答
  • 车间调度问题

    万次阅读 多人点赞 2018-11-21 14:18:13
    作业车间调度问题描述 作业车间调度问题(Job Shop Scheduling, JSP)是最经典的几个NP-hard问题之一。其应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等。 JSP问题描述:一个...

    作业车间调度问题描述

    作业车间调度问题(Job Shop Scheduling, JSP)是最经典的几个NP-hard问题之一。其应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等。

    JSP问题描述:一个加工系统有M台机器,要求加工N个作业,其中,作业i包含工序数为Li。令,则L为任务集的总工序数。其中,各工序的加工时间已确定,并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序,约束条件被满足的同时,使性能指标得到优化。

    作业车间调度需要考虑如下约束:

    Cons1:每道工序在指定的机器上加工,且必须在其前一道工序加工完成后才能开始加工;

    Cons2:某一时刻1台机器只能加工1个作业;

    Cons3:每个作业只能在1台机器上加工1次;

    Cons4:各作业的工序顺序和加工时间已知,不随加工排序的改变而改变。

    问题实例

    下面给出作业车间调度问题的一个实例,其中每个工序上标注有一对数值(m,p),其中,m表示当前工序必须在第m台机器上进行加工,p表示第m台机器加工当前工序所需要的加工时间。(注:机器和作业的编号从0开始)
    jop0=[(0,3),(1,2),(2,2)]
    jop1=[(0,2),(2,1),(1,4)]
    jop2=[(1,4),(2,3)]
    在这个例子中,作业jop0有3道工序:它的第1道工序上标注有(0,3),其表示第1道工序必须在第0台机器上进行加工,且需要3个单位的加工时间;它的第2道工序上标注有(1,2),其表示第2道工序必须在第1台机器上进行加工,且需要2个单位的加工时间;余下的同理。总的来说,这个实例中共有8道工序。
    该问题的一个可行解是L=8道工序开始时间的一个排列,且满足问题的约束。下图给出了一个可行解(注:该解不是最优解)的示例:
    在这里插入图片描述

    使用深度搜索解决车间调度问题

    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int totalStep,minTime;
    int n,m;
    int Step[105];
    struct Job
    {
        int machine;
        int len;
    } job[105][105];
    int jobEnd[105][105];
    int jobStep[105];
    int machineWorkTime[105];
    struct Recording
    {
        int start;
        int ed;
        int job;
        int machine;
    } best[105],now[105];
    void init()
    {
        totalStep=0;
        minTime = 999999999;
        memset(jobStep,0,sizeof(jobStep));
        memset(machineWorkTime,0,sizeof(machineWorkTime));
        memset(best,0,sizeof(best));
        memset(jobEnd,-1,sizeof(jobEnd));
    }
    void dfs(int step,int time)
    {
        if (time>=minTime) return;
        if (step == totalStep)
        {
            minTime = time;
            for (int i=0; i<totalStep; i++)
                best[i]=now[i];
            /*int gantt[105][105];
            for (int i=0;i<totalStep;i++)
            {
                for (int j=best[i].start;j<best[i].ed;j++)
                {
                    gantt[best[i].machine][j]=best[i].job;
                }
            }
            for (int i=0;i<m;i++)
                for (int j=0;j<minTime;j++)
                    printf("%d%c",gantt[i][j],j==minTime-1?'\n':' ');
                printf("\n");*/
            return;
        }
    
        for (int i=0; i<n; i++)
        {
            int j = jobStep[i];
            if (j >= Step[i]) continue;
            int thisMachine = job[i][j].machine;
            now[step].machine = thisMachine;
            now[step].job = i+1;
            int temp =  machineWorkTime[thisMachine];
            int beginTime = max(jobEnd[i][j-1],machineWorkTime[thisMachine]);
            now[step].start = beginTime;
            machineWorkTime[thisMachine] =beginTime + job[i][j].len;
            jobEnd[i][j] = now[step].ed = machineWorkTime[thisMachine];
            jobStep[i]++;
            //printf("%d %d %d\n",step,i,j);
            dfs(step+1, max(time,machineWorkTime[thisMachine]) );
            jobStep[i]--;
            machineWorkTime[thisMachine]=temp;
        }
    }
    int main()
    {
        printf("输入工作数量:");
        scanf("%d",&n);
        printf("输入机器数量:");
        scanf("%d",&m);
        init();
        for (int i=0; i<n; i++)
        {
            printf("输入工作%d的步骤数量:",i);
            scanf("%d",&Step[i]);
            totalStep+=Step[i];
            for (int j=0; j<Step[i]; j++)
            {
                printf("步骤%d运行于哪个机器,消耗时间:",j+1);
                scanf("%d%d",&job[i][j].machine,&job[i][j].len);
            }
    
        }
        dfs(0,0);
        printf("最短时间为:%d\n",minTime);
    
        int gantt[105][105];
        for (int i=0; i<totalStep; i++)
        {
            for (int j=best[i].start; j<best[i].ed; j++)
            {
                gantt[best[i].machine][j]=best[i].job;
            }
        }
    
        for (int i=0; i<m; i++)
            for (int j=0; j<minTime; j++)
                printf("%d%c",gantt[i][j],j==minTime-1?'\n':' ');
    }
    
    展开全文
  • 经典作业车间调度问题 在传统车间调度模型中,假设工序加工所需要的资源是不具备柔性的资源,工件的所有工序的加工机器是唯一的,且机器顺序是已知的,则可通过确定工序在每台机器上的加工顺序来优化完工时间等系统...

    经典作业车间调度问题

    在传统车间调度模型中,假设工序加工所需要的资源是不具备柔性的资源,工件的所有工序的加工机器是唯一的,且机器顺序是已知的,则可通过确定工序在每台机器上的加工顺序来优化完工时间等系统目标。随着大批量连续生产时代正逐渐被适应市场动态变化的多品种、小批量离散生产所替代,一个制造企业的生存能力和竞争能力在很大程度上取决于它是否能在较短的生产周期内,生产出较低成本、较高质量的多个产品品种的能力。
    在这里插入图片描述

    柔性作业车间调度问题

    柔性作业车间调度问题(flexiblejobshopschedu-lingproblem,FJSP)也就成为研究重点,它是JSP问题的扩展,工件的每道工序可以在多台机器上进行加工,且在每台机器上的加工时间不一定相同。实际生产中可以按照资源负荷情况,灵活地进行资源的选择,提高加工的灵活性。工件的每道工序可以在多台机器上加工的情况在实际生产中有明显的优点:
    (1)提高设备的利用率,机床一旦空闲就可以安排工件进行加工,减少设备闲置和等待的时间;
    (2)具有维持生产稳定的能力,当一台或多台机器发生故障时,工序可以绕过故障机器,在其他机器上进行加工,使生产得以继续,保证生产的稳定;
    (3)提高产品质量和缩短生产周期,与经典的JSP模型相比,同一工件的多道工序可以在同一台机床上连续进行加工,减少了中间装卸和搬运等而造成的时间消耗

    柔性作业车间调度问题是一个NP-hard问题,不可能找到精确求得FJSP最优解的多项式时间算法。研究人员为解决这个难题已付出了几十年的努力,但至今最先进的算法仍很难得到规模较小问题的最优解。近十几年以来,通过模拟自然界中生物或物理过程而发展起来的元启发式算法用于研究FJSP,如遗传算法(geneticalgorithms,GA)、蚁群优化算法(antcolonyoptimization,ACO)、禁忌搜索算法(tabusearch,TS)、粒子群优化算法(particleswarmoptimization,PSO)、模拟退火算法(simulatedannealing,SA)、DNA算法等

    在这里插入图片描述

    柔性作业车间调度问题特点

    1.计算复杂
    柔性作业车间调度问题是作业车间调度问题的扩展,它不仅需要确定工序加工的顺序,还要给每道工序分配机器,是比JSP更为复杂的NP-hard问题

    2.多目标
    实际生产中经常考虑多项性能指标要求,且各项要求可能彼此冲突。常用的调度性能指标包括:最大完工时间、交货期、机器总负荷、生产成本、延迟或拖期、库存等。
    3.不确定性
    实际制造中存在广泛的不确定性因素,如机器故障、操作人员的熟练程度、原材料的差异、刀具磨损等因素的影响,确定的加工信息很少能获得。
    4.动态性
    实际生产制造过程是一个动态的过程,加工工件通常是依次进入待加工状态的,各种工件不断进入制造系统接受加工,已加工完的工件又不断地离开制造系统。
    目前车间静态、不确定随机、动态调度范围的定义存在多种不同的分类模型,而这些模型直接影响解决问题的复杂性,因此要求模型简单,接近实际生产过程。一种简单、实用的动态和不确定调度分类模型如图1.3所示,图中可清晰区分静态调度、动态调度、多目标调度、不确定调度、多目标不确定调度的范围
    在这里插入图片描述

    展开全文
  • 【车间调度】基于模拟退火求解车间调度问题.md
  • 【车间调度】基于模拟退火算法求解车间调度问题matlab源码.md
  • 【车间调度】车间调度问题的分类

    千次阅读 2021-01-28 11:16:28
    车间调度问题的分类 根据工件和车间构成不同,车间调度问题可分为以下几种 1.单机调度问题 在单机调度问题(S,SMP)中,加工系统只有一台机床,待加工的工件有且仅有一道工序,所有工件都在该机床上进行加工。...

    本系列为自己学习调度相关知识的记录,如有误请指出,也欢迎调度方向的小伙伴加我好友共同交流。

    车间调度问题的分类

    根据工件和车间构成不同,车间调度问题可分为以下几种

    1.单机调度问题

    在单机调度问题(Single machine scheduling problem,SMP)中,加工系统只有一台机床,待加工的工件有且仅有一道工序,所有工件都在该机床上进行加工。此问题是最简单的调度问题,当生产车间出现瓶颈机床时的调度就可视为此调度问题。

    2.并行机调度问题

    在并行机调度问题(parallel machine scheduling problem ,PMP)中,加工系统中有多个完全相同的机床,每个工件只有一道工序,工件可以在任意一台机床上进行加工。

    3.开放车间调度问题

    在开放车间调度问题(open shop scheduling problem,OSP)中,每个工件的工序之间的加工顺序是任意的。工件的加工可以从任何一道工序开始,在任何一道工序结束。工件的加工没有特定的技术路线约束,各个工序之间没有先后关系约束

    4.流水车间调度问题

    在流水车间调度问题(flow shop scheduling problem ,FSP)中,加工系统有一组功能不同的机床,待加工的工件包含多道工序,每道工序在一台机床上加工,所有工件的加工路线都是相同的。每个工件工序之间有先后顺序约束

    5.作业车间调度问题

    在作业车间调度问题(job shop scheduling problem ,JSP)中,加工系统有一组功能不同的机床,待加工的工件包含多道工序,每道工序在一台机床上加工,工件的加工路线互不相同,每个工件工序之间有先后顺序约束。

    这几种调度以及他们的扩展问题都可以用三元组α/β/γ的形式进行描述,其中

    • α表示机器的加工环境,
    • β表示工件的加工特性,
    • γ表示加工性能指标

    鉴于流水车间和作业车间的特殊性、典型性和重要性,通常将其称为基本调度问题。一般用n/m/A/B将其简明表示,其中

    • n表示工件数,
    • m表示机器数,
    • A表示工件流经机器的类型(作业车间用G表示,流水车间用F表示,置换流水车间用P表示等),
    • B表示性能指标(如 C m a x C_{max} Cmax L m a x L_{max} Lmax T m a x T_{max} Tmax等)。
    展开全文
  • 【车间调度】基于PSO求解6X6的车间调度问题matlab 源码.md
  • 车间调度问题.rar

    2020-07-15 21:52:56
    这是关于车间调度问题的matlab算法,内容是包含注释的源代码,方便大家更好地读懂程序,采用的是改进过后的PSO算法,
  • 【车间调度】基于matlab改进蛙跳算法求解车间调度问题【含Matlab源码 073期】.zip
  • 混合NSGA-Ⅱ算法求解多目标柔性作业车间调度问题
  • 基于遗传算法车间调度问题matlab程序 基于遗传算法车间调度问题matlab程序 基于遗传算法车间调度问题matlab程序 基于遗传算法车间调度问题matlab程序
  • 智能车间调度问题,利用遗传算法更好的解决车间调度问题
  • 针对两机无等待流水车间调度问题, 提出目标函数最大完工时间最小化的快速算法, 并给出算法的复杂度. 分析两机无等待流水车间调度问题的排列排序性质, 证明了两机无等待流水车间调度问题的可行解只存在于排列排...
  • 本系列为自己学习调度相关知识的记录,如有误请指出,也欢迎调度方向的小伙伴加我好友共同交流。 1.多约束性在通常情况下,工件的...可以利用数学规划、离散系统建模与仿真、排序理论等方法对车间调度问题进行研.

    本系列为自己学习调度相关知识的记录,如有误请指出,也欢迎调度方向的小伙伴加我好友共同交流。

    1.多约束性在通常情况下,工件的加工路线是已知的,并且受到严格的工艺约束,使得各道工序在加工顺序上具有先后约束关系;同时,工件的加工机器集是已知的,工件必须按照工序顺序在可以选择的机床上进行加工。
    2.离散性车间生产系统是典型的离散系统,其调度问题是离散优化问题。工件的开始加工时间、任务的到达、订单的变更,以及设备的增添或故障等都是离散事件。可以利用数学规划、离散系统建模与仿真、排序理论等方法对车间调度问题进行研究。
    3.计算复杂性车间调度是一个在若干等式和不等式约束下的组合优化问题,从计算时间复杂度看是一个NP-hard问题。随着调度规模的增大,问题可行解的数量呈指数级增加。很简单的例子如:工件和机器的数量均为10的单机车间调度问题,当单纯考虑加工周期最短时,可能的组合数就已达到 ( 10 ! ) 10 (10!)^{10} (10!)10.
    4.不确定性在实际车间调度中有很多随机因素,如:工件到达时间的不确定性,工件的加工时间随着不同的加工机器也有一定的不确定性。而且系统中常有突发事件,如:紧急订单插入、订单取消、原材料紧缺、交货期变更、设备发生故障等。
    5.多目标性在不同类型的制造企业和不同的生产环境下,调度目标往往形式多样、种类繁多。如:完工时间最小、交货期最早、设备利用率最高、成本最低、在制品库存量最少等。多目标性的含义:一个是目标的多样性;另一个是多个目标需要同时得到满足,并且各个目标之间往往是相互冲突的.

    展开全文
  • 柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)的描述如下:n个工件(J1,J2....JnJ_1,J_2....J_nJ1​,J2​....Jn​)要在m台机器(M1,M2.....MmM_1,M_2.....M_mM1​,M2​.....Mm​)上加工;...
  • 作业车间调度问题描述 作业车间调度问题(Job Shop Scheduling, JSP)是最经典的几个NP-hard问题之一。其应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等。 JSP问题描述:一个...
  • 车间调度问题的研究始于20世纪50年代。在1954年,Johnson提出了解决n/2/F/CmaxC_{max}Cmax​和部分特殊的n/3/F/CmaxC_{max}Cmax​问题的有效优化算法,代表经典调度理论研究的开始。不过直到20世纪50年代...
  • 本文讨论的任务车间调度问题是一个典型的NP完全问题,也是最难解的组合优化问题之一。虽然本题给出的工件(墙纸)数n、机器数m及工序(印刷颜色)数l较小,但可以看到,利用经典整数规划的方法求解该问题还是存在着...
  • 改进遗传算法解决柔性作业车间调度问题,田旻,刘人境,柔性作业车间调度问题是经典作业车间调度问题的深入和扩展,为生产过程中作业车间调度的资源受限问题提供了更加切实可行的方案。
  • 针对置换流水车间调度问题,提出了一种基于强化学习Q-Learning调度算法.通过引入状态变量和行为变量,将组合优化的排序问题转换成序贯决策问题,来解决置换流水车间调度问题.采用所提算法对OR-Library提供Flow-shop...
  • 通过用标准车间调度问题对该算法的性能进行检验;然后把该算法用于解决基于事件驱动调度策略的动态车间调度问题;仿真结果表明GSPSO算法具有快速的收敛性和可行性,能对生产过程中发生的动态事件进行合理调度。
  • 介绍了车间调度问题的含义和特点,总结了近年来出现的车间调度数学模型和研究方法,分析了研究中存在的问题,并指出了解决途径与进一步的研究方向.
  • 采用粒子群优化算法求解典型的NP-Hard问题——作业车间调度问题,优化目标为平均流动时间,希望对大家研究该问题有帮助!
  • 自己写的用遗传算法求解柔性作业车间调度问题,可直接运行,文件内含有10个FJSP基础算例,在help.cpp文件中修改算例文件名称即可运行其他算例。
  • 物流运筹实务课程设计 题目置换流水车间调度问题的 MATLAB 求解 置换流水车间调度问题的 MATLAB 求解 第 1 页 共 32 页 目 录 一 前 言 5 二 问 题 描 述 6 三 算 法 设 计 7 四 实 验 结 果 15 第 2 页 共 32 页 摘...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,734
精华内容 2,693
关键字:

车间调度问题