APS开源引擎介绍

最近做排程项目,整理了一些开源的以及商业的引擎,运用好引擎其实可以简化开发,让开发人员可以专注于业务设计,以下整理的资料大多来自于维基百科和chatgpt,希望能对aps开发做一些帮助。

1 dream

https://github.com/Nexedi/dream

dream是开源制造业erp软件erp5的计划引擎,由欧洲公司nexedi研发,源于欧盟在先进制造技术领域的一个研究项目,该研究项目是为了保证欧盟制造业在21世纪的先进性和领先地位

功能类似sap apo,也是唯一一个同时支持物流建模仿真,供应链网络计划和生产排程的开源系统

dream使用离散仿真技术来进行物流建模仿真,供应链网络计划和生产排程,系统庞大,算法高度复杂,支持优化结果计算

dream的缺点是输入输出都是使用文本文件,和erp系统集成不是很好,而且开源的只是第一版,之后的版本就没有继续开源,要是根据项目要求对dream进行定制,难度相当大。

2 frepple

https://github.com/frePPLe/frepple

frepple是一个历史悠久的开源生产排程软件,由知名aps公司i2的前研发人员创立frepple底层算法层使用了c++,上层业务建模层使用python/django,通过pythoh调用C++库进行排程,这个架构非常适合云排产

frepple的算法层大量使用了c++的模版编程,同时架构设计非常复杂,读懂代码就很有困难

另外,frepple的开源版本只是做演示,给商业版引流,自带算法本身非常简单,只有千来行代码(知名国际aps软件比如i2/apo,都有十几万甚至几十万行代码)也就是说排程特别简单的企业可以用frepple,但是没有必要,排程复杂的企业,frepple自带算法根本不能满足,这就是为什么尽管历史悠久,但是frepple一直没有火起来的原因

除非是特别简单的排程项目,否则算法都要重写以满足项目要求,有知名欧洲软件外包公司年薪百万招聘清华博士组成团队对frepple的算法进行复杂排程逻辑改造,最后失败告终。

3 OptaPlanner与Google OR-Tools

OptaPlanner

OptaPlanner - The fast, Open Source and easy-to-use solver

基于Apache开源软件协议,该协议对商用友好,因此可以自由地将该技术的部分或全部应用于商用软件项目中。作为开源项目一直维护至今,其版本发布仍十分高效,除进行一些对用户透明不可视的算法与架构优化外,不时还有极具价值的新功能与新特征发布,如7.09版本发布的多线程支持,最大程度上提高对CPU的利用率。

OptaPlanner是使用Java语言开发,是基于纯Java技术。因此,使用它的时候也只需要使用Java语言本身的特性,即可满足几乎所有基本的建模、开发及求解过程;而无需使用其它第三方的技术或框架。当然当你在实际的工程实践中,还是需要依赖强大的Java生态圈,才能让项目事半功倍。例如通过第三方组件实现日志,数据的持久化、Web服务等。

OptaPlanner的评分逻辑,需要使用Drools作为规则描述语言,实现约束的评分。事实上OptaPlanner同时支持Java语言实现约束评分的,即Easy Java Score Calculation与Incremental Java Score Calculation,使用这两种评分方式,评分逻辑可直接使用Java语言实现。仅需通过POJO即可对业务实体进行建模,通过Java程序代码即可描述业务约束。Optaplanner的核心程序以Jar包方式提供;当然你也可以获取它的源代码,从源代码级把它的核心集成到你自己的系统中去。但作为商业软件项目,此方法并非最佳实践,直接使用官方发布的Jar 包即可。Optaplanner不支持MiniZinc作为建模语言,OR-Tools则支持该种约束建模语言。

从另一个角度来看,纯Java技术实现的OptaPlanner,对使用环境起到简化作用的同时,又会形成了一种限制。例如对于一些非Java技术开发的系统(例如一些旧系统),要与OptaPlanner集成到同一个程序中,则无法实现尝试结合。对于这种情况,解决办法是将OptaPlanner独立成一个Web服务,以WebAPI 的方式对外提供服务。

Google OR-Tools

developers.google.com

Google OR-Tools, 顾名思义是由Google提供的一套运筹规划的运算工具,它针对不同的规划场景,提供了不同的求解器(以组件方式提供)。OR-Tools同样是基于Apache开源软件协议。OR-Tools的讨论区讨论相当热烈,主要原因是它的使用方法与传统商用的求解器(如Cplex, Gurobi等)相当类似,因此相当一些运筹学的学者、学生对该软件比较感兴趣。

OR-Tools是用于解决组合优化问题的开源软件,它的目的是从众多可能方案中寻求最佳的解决方案,比如解决以下的问题:线性规划与整数规划(Linear Optimization&Integer Optimization)、网络流问题(Network Flows) 、路径规划问题(Routing) 、装箱问题(Bin Packing) 、调度问题(Scheduling)

OR-Tools内核是使用**C++**开发,因此,其兼容性相对OptaPlanner来说好很多。目前Google OR-Tools支持C++, C#, Java和Python四种语言接口。即它具有动态链接库存(DLL), Jar包和Python包三种提供提供形式。当然因为它的原始形式是dll文件,通过过Java对它进行调用的时候,就需要通过JNI对它进行装载。因为OR-Tools提供丰富的兼容形式,因此,与不同系统集成较容易。可直接将它的源代码或DLL嵌入到自己的系统中去。当然,如果使用源代码的方式集成,只能嵌入到C++开发的系统中。

在系统集成方面,因为OR-Tools接口相对开放,集成的问题则基本上不存在任何问题。其核心(规划求解器)可以作为系统的一个组件存在于任何系统中;也可以将其封装成一个服务对外提供服务。

对比:

OptaPlanner更偏向于面向对象,使用OptaPlanner进行系统开发的时候(例如开发APS系统),如其它商用软件一样,先对业务进行分析,设计出具体的业务实体,识别出需要规则的实体和因素(字段),提炼出业务规则,归纳出哪些规则是硬约束,哪些是可以优化的软约束。然后根据OptaPlanner的固定对象结构模式,建立Planning Entity, Planning Variable,Problem Fact和Solution等类;并配置好求解器的各种参数。整个核心系统的设计就差不多完成了。

Google OR-Tools偏向于传统的数据建模。OR-Tools除了同样需要进行业务分析与设计外,还需要加多一步工作 - 数学建模。因为OR-Tools求解规划问题时,输出的必须是一个完整的数学模型。也就是在使用OR-Tools进行系统开发时,需要先进行业务分析设计,获得各种业务要素和约束后,需要对这些业务要素进行数学建模,并将这个模型以程序语言(Python, C++, Java, C#)或MiniZinc进行模型描述。然后才能启动规划求解器进行寻找优势方案。实现OptaPlanner在使用其求解器进行规划求解时,也需要有相应的数学模型的,只不过它可以在求解之前,把用Java对象表示的业务模型,转换成数学模型;而这个步骤对使用都来说是透明的,因此无需关心。

基于两者建模方式上的差别,对于偏向于理论研究、学习的学者来说,OR-Tools更接近于他们日常接触的各类规模模型,与CPLEX和Gurobi等知名商用(有免费的学术用途授权)求解器的应用方法与设计思想均较接近。因此,对于一些考研类的应用场景,OR-Tools来得更直接。

而OptaPlanner则更趋向解决具体的业务问题,从其诞生的背景可以得知,它主要是为解决具体问题而生的。尽管OptaPlanner与OR-Tools其核心是相当接近的,都是通过各种启发式算法,对NP-Hard问题寻找相对最优解。但OptaPlanner考虑到非运筹专业人员的数学功底,对问题多做了一层封装,将程序中描述业务问题的各种对象,转换成相应的规划模型,再进行规划求解。从而在商用软件开发环境中,普通的程序设计人员,只需要关注具体的业务细则,根据OptaPlanner提供的模式,建立合理的对象模型,来反映业务模型,确保这些业务模型能准确地反映业务需求即可。而无需再将这些业务模型转换成可运筹学上数学规划所需的数学规划模型。从而大大降低了规划程序的开发难度。

4 Choco Solver

choco-solver.org

Choco Solver是一个Java约束编程库,用于解决各种约束满足问题。约束满足问题是一个在给定的一组约束下,寻找变量值的过程,以使得所有约束得到满足。Choco Solver的目标是提供一个简单而强大的API,可用于建模和解决各种约束满足问题,例如排程问题,布尔满足问题等。 Choco Solver库包含一系列Java类和接口,这些类和接口可以帮助用户定义问题模型和约束,选择求解器以解决问题,以及访问模型的解决方案。Choco Solver提供了丰富的API,用于定义变量以及与变量相关的约束。例如,用户可以定义整数变量、布尔变量和字符串变量,并添加等式约束、不等式约束、全局约束等。 Choco Solver还提供了一个求解器框架,它允许用户选择不同的求解器,包括回溯搜索、局部搜索、分支界限等。用户可以使用这些求解器来解决各种约束满足问题,包括排程问题、时间表问题、集合分区问题等。此外,Choco Solver还支持多线程求解和对不完整数据的支持。 除了API和求解器框架外,Choco Solver还提供了丰富的工具和支持。例如,它提供了图形用户界面(GUI)工具,可用于可视化问题模型和解决方案。它还提供了许多示例代码和文档,以帮助用户更好地了解Choco Solver的使用。总之,Choco Solver是一个强大的Java约束编程库,可用于解决各种约束满足问题。它提供了丰富的API和求解器框架,支持多线程求解和对不完整数据的处理。如果需要解决复杂的约束满足问题,Choco Solver是一个值得考虑的选项。

当您使用Choco Solver时,需要遵循以下步骤:

安装Java:确保您的计算机已安装Java,因为Choco Solver是一个Java库

下载Choco Solver:从Choco Solver的官方网站上下载最新版本的库。

导入Choco Solver:将下载的Choco Solver库导入到您的Java项目中。

创建模型:使用Choco Solver,您需要为要解决的问题定义一个模型。您可以使用Choco Solver API来创建、定义和控制模型和变量。例如,您可以定义整数变量、布尔变量和字符串变量。

添加约束:一旦您定义了模型和变量,您可以使用Choco Solver API来添加约束。约束是问题的限制条件,可以是等式或不等式。例如,您可以添加约束,以便确保所有变量都在特定范围内或具有特定的关系。

定义目标:在某些情况下,您可能需要找到最佳解决方案。在这种情况下,您可以使用Choco Solver API定义一个目标,例如最小化或最大化一个变量。

解决问题:最后,您可以使用Choco Solver API来解决问题。您可以使用不同的求解器来解决问题,例如深度优先搜索或广度优先搜索。解决问题后,您可以访问变量和约束的值,以及目标函数的值(如果有)。

5 Gecode

www.gecode.org

Gecode是一个强大的开源软件框架,用于求解约束优化问题。它是用**C++**编写的 ,提供了一组强大的约束求解库,包括多种求解器和约束类型。Gecode支持多重搜索策略和变量选择策略,能够解决各种约束优化问题,例如排班问题、时间表问题、调度问题等。Gecode具有高度可扩展性,支持插件机制,使得开发人员可以自行添加新的约束类型和求解器。

此外,Gecode还提供易于使用的API和文档,使得开发人员能够快速上手使用该框架。Gecode在学术界和工业界都有广泛的应用,特别是在计划、调度和优化等领域。如果您是约束优化问题领域的开发人员,Gecode是一个不可或缺的工具。

APS问题(Assignment Problem with Separability constraints)是一种NP难问题,它可以通过Gecode来求解。APS问题是一种组合优化问题,它的目标是在给定的一组任务和一组工作者之间,找到一个最佳的匹配方案,以最小化总的成本或者最大化总的收益。

以下是使用Gecode求解APS问题的一般步骤:

定义变量和目标函数:首先,我们需要定义一个IntVarArray类型的变量数组,用于表示任务的分配情况。然后,我们需要定义一个IntVar类型的变量,用于表示总的成本或者总的收益。

定义约束条件:我们需要定义一些约束条件,以满足分配问题的限制。例如,我们可以定义分配方案中每个任务只能分配给一个工作者,每个工作者只能完成一个任务等等。

定义搜索引擎:我们需要定义一个搜索引擎,以搜索最优的分配方案。在Gecode中,我们可以使用多种搜索引擎,如DFS、BAB等。

开始搜索:最后,我们需要调用Gecode提供的搜索函数来开始求解。

6 SCIP

www.scipopt.org

SCIP(Solving Constraint Integer Programs)是一款用于求解混合整数规划(MIP)和整数规划(IP)问题的开源优化软件。SCIP支持线性规划(LP)求解器和各种分支定界(B&B)策略,同时还内置了各种启发式和可削减平面的库,可用于解决大规模、复杂的数学规划问题。 SCIP的特点如下:

SCIP提供灵活的插件接口包括java、python等等,也能与matlab、excel集成,可以方便地添加新的分支策略、割平面等算法,也可以方便地与其他软件集成。SCIP支持多线程求解,可以有效地利用多核处理器,提高求解效率。SCIP提供了丰富的输出信息,可以方便地调试和分析模型求解过程。SCIP支持GAMS、AMPL、Zimpl、MPS、LP等多种模型输入格式,方便用户使用。

另外,SCIP还开发了一些基于其内核的高级求解器,如GCG、SoPlex等,可用于解决一些特定的优化问题。总的来说,SCIP是一款功能强大、灵活性高、易于扩展和集成的开源优化软件。

SCIP可以用于求解各种优化问题,包括APS问题。APS问题是一种NP-hard问题,通常涉及到工人的分配和任务的分配,目标是最小化线上平衡时间或最大化生产效率等。在SCIP中,可以使用整数规划(IP)或混合整数规划(MIP)模型来描述APS问题,并利用SCIP的分支定界(B&B)算法求解最优解。APS问题的IP或MIP模型通常包括以下方面的约束条件和目标函数

约束条件:

工人的分配约束:每个工人在任何时候只能做一项任务。

任务的分配约束:每个任务必须在规定的时间内完成,并且只能由一个工人完成。

前置任务约束:如果某个任务必须在另一个任务之前完成,则应该包括前置任务约束。

平衡约束:每个线上工作站的工作时间应该接近于其他工作站的工作时间。

目标函数:

最小化线上平衡时间(Makespan):最长的线上工作站的工作时间。

最小化空闲时间:所有工作站的总空闲时间之和。

需要注意的是,APS问题的解决方案通常需要结合具体的生产环境和实际工艺流程进行设计和实现。在使用SCIP求解APS问题时,可以根据实际情况对模型进行调整和优化,以获得更好的求解效果。

7 coin-or

COIN-OR: Computational Infrastructure for Operations Research – Open-source Software for the Operations Research Community

Coin-or是一个计算基础设施,旨在为运筹学及其相关领域提供各种优化工具和软件,包括线性规划、整数规划、非线性规划、网络流等。它是一个由学术界、工业界和政府机构的专业人士组成的开源项目,所有的工具都是基于开源许可证发布的,可以在个人和商业项目中免费使用。Coin-or还提供了详细的文档、示例和测试数据,以便用户更好地了解和使用这些工具。

Coin-or拥有强大的计算能力和可扩展性,能够处理大规模问题,并且可以定制化。Coin-or不仅可以帮助研究人员解决实际问题,还可以被工业界和政府机构用于优化生产和服务等方面,以提高效率和降低成本。Coin-or已经成为全球运筹学和优化领域的重要基础设施之一,得到了广泛应用和认可。

Coin-or可以通过提供各种优化工具和算法来解决APS(高级计划与排程)问题,特别是整数规划(IP)和混合整数规划(MIP)工具。在具体应用中,你可以使用Coin-or工具根据具体的APS问题进行定制化求解。具体的流程如下

建立数学模型:将APS问题转化为数学模型,确定目标函数、决策变量和约束条件。

选择合适的算法:根据数学模型的特点,选择合适的Coin-or算法来求解问题。Coin-or中的一些工具,例如CBC和Bonmin,都是比较常用的求解器。

设计求解策略:由于APS问题通常比较复杂,需要设计合适的求解策略来提高求解效率和精度。例如,可以使用分支定界、割平面和可行性剪枝等技术来加速求解。

实现求解:将数学模型和求解策略实现在Coin-or中,进行求解并得到优化结果。

评估和优化:对求解结果进行评估和优化,查看是否满足预期的需求和目标。如果需要进一步优化,则可以重新调整模型和求解策略,重复以上步骤。

总之,Coin-or可以提供一个可靠、高效、定制化的优化平台,为解决APS问题提供有力支持。

商用aps软件或者引擎推荐:

SAP APO:它是SAP公司的供应链管理软件,它可以帮助企业通过对生产计划、库存管理、物流运输等环节的优化,提高生产效率和运营效率。该软件包括了多个模块,如需求计划、生产计划、物流计划、网络计划等等,能够全面覆盖企业的供应链管理需求。另外,SAP APO可以和SAP ERP等软件进行集成,实现更加协同和高效的运营管理。

ASCP:它是Oracle公司的一款高级供应链计划软件,是Oracle E-Business Suite的重要组成部分之一。ASCP能够帮助企业规划和优化整个供应链,例如生产计划、采购计划、库存管理等等。该软件还具备高级的算法和模型,能够对复杂的生产和库存问题进行快速的解决,从而提高了企业的运营效率和客户满意度。

Preactor:它是一款排程软件,可以帮助企业实现生产排程和资源分配的优化,从而提高生产效率和降低成本。Preactor支持多种排程模式,例如离散型、流水型、混合型等等,可以适应不同的生产环境。此外,Preactor还具备智能排程和预测分析功能,能够帮助企业更好地应对变化和不确定性。

JDA Software:它是一款全球领先的供应链管理和物流管理软件,可以帮助企业实现全球范围内的供应链和物流管理。JDA Software包括多个模块,如需求计划、库存管理、物流管理、运输管理等等,能够全面覆盖企业的供应链管理需求。该软件还具备高级的算法和模型,能够对复杂的供应链问题进行精确的解决,从而提高了企业的运营效率和客户满意度。

Flexsche:它是一款排程和生产计划软件,可以帮助企业实现生产排程和资源优化,从而实现更高效的生产和运营管理。Flexsche支持多种排程模式,如离散型、流水型、多阶段型等等,能够适应不同的生产环境。此外,Flexsche还具备智能算法和实时数据分析功能,能够帮助企业更好地应对生产环境的变化和不确定性。

整体对比:

软件/引擎dreamfreppleOptaPlannerGoogle OR-ToolsChoco SolverGecodeSCIPcoin-orSAP APOASCPPreactorJDA SoftwareFlexsche
官网http://dream-simulation.eu/https://frepple.com/OptaPlanner - The fast, Open Source and easy-to-use solverdevelopers.google.comchoco-solver.orgwww.gecode.orgwww.scipopt.orghttps://www.coin-or.org/
开发语言PythonPythonJavaC++JavaC++C语言C++ABAPJavaJavaJavaC++和Java
开源
支持的语言PythonPythonJavaJava C++ PythonJavaJavaC++C++ABAPJava
求解器类型基于约束编程的求解器基于约束编程的求解器基于约束编程的求解器基于约束编程的求解器基于混合整数线性规划的求解器基于混合整数线性规划的求解器
算法贪心、局部搜索和元启发式算法等线性规划、整数规划、半连续规划、约束编程、局部搜索特别是Tabu搜索以及混合整数规划等深度优先搜索、广度优先搜索、最小冲突搜索等贪心搜索、最小冲突搜索、随机搜索、局部搜索等整数规划、混合整数规划、约束整数规划、多目标问题等整数规划、混合整数规划、约束整数规划、多目标问题等使用线性规划和整数规划等优化算法、启发式算法线性规划和整数规划等优化算法启发式算法启发式算法
支持的业务模型支持物流建模仿真、供应链网络计划、生产排程生产排程排班、路径规划和资源分配等路由、排班、车辆路径规划、工厂调度等时间表调度、资源分配和物流规划等动态调度、机器学习、网络设计等自动化设计、智能制造、能源等航空、化工、制造等物流和供应链规划物流和供应链规划专注于生产计划排程提供全面的供应链规划和优化方案提供运输计划和资源调度方案
用户群体受Java社区欢迎受Google开发者,特别是在路由、日程安排和计划领域受Java开发者和学术界欢迎受欧洲学术界欢迎受科学和工程领域欢迎受研究机构和大型企业欢迎大型企业和组织Oracle E-Business Suite的客户中小型制造企业面向全球的大型企业交通和物流领域的组织
社区和文档比较全面的文档和社区支持比较全面的文档和社区支持文档和社区支持相对较少文档和社区支持相对较少文档和社区支持相对较多文档和社区支持相对较多具有庞大的用户社区和良好的技术支持,同时也有丰富的文档和培训资源具有庞大的用户社区和良好的技术支持,同时也有丰富的文档和培训资源具有较小的用户社区,但官方文档和技术支持仍然是可用的用户社区和技术支持资源较为丰富具有较小的用户社区,但官方文档和技术支持仍然是可用的
特点输入输出都是使用文本文件,和erp系统集成不是很好,而且开源的只是第一版,之后的版本就没有继续开源,要是根据项目要求对dream进行定制,难度相当大架构设计非常复杂,frepple的开源版本只是做演示,给商业版引流,自带算法本身非常简单,只有千来行代码纯Java技术,使用它的时候也只需要使用Java语言本身的特性,即可满足几乎所有基本的建模、开发及求解过程;而无需使用其它第三方的技术或框架。还是需要依赖强大的Java生态圈,才能让项目事半功倍。偏向于传统的数据建模。OR-Tools除了同样需要进行业务分析与设计外,还需要加多一步工作 - 数学建模,对于偏向于理论研究、学习的学者来说,OR-Tools更接近于他们日常接触的各类规模模型是一个Java约束编程库,包含一系列Java类和接口,这些类和接口可以帮助用户定义问题模型和约束,选择求解器以解决问题,以及访问模型的解决方案。Choco Solver提供了丰富的API,用于定义变量以及与变量相关的约束。强大的开源软件框架,供易于使用的API和文档,使得开发人员能够快速上手使用该框架。Gecode在学术界和工业界都有广泛的应用,特别是在计划、调度和优化等领域。用于求解混合整数规划(MIP)和整数规划(IP)问题的开源优化软件,时还内置了各种启发式和可削减平面的库,可用于解决大规模、复杂的数学规划问题计算基础设施,旨在为运筹学及其相关领域提供各种优化工具和软件,包括线性规划、整数规划、非线性规划、网络流等。它是一个由学术界、工业界和政府机构的专业人士组成的开源项目

参考资料

开源生产排程aps(Advanced Planning and Scheduling)软件介绍_开源aps_lijianhua_9712的博客-CSDN博客

本文链接:https://my.lmcjl.com/post/4396.html

展开阅读全文

4 评论

留下您的评论.