example_3.md 17.5 KB

【LP专题-3】生产调度:Flow Shop 调度优化下界估计问题

使用过程提示

Tips:

  • 您可点击右下角“下一步”,查看后续的建模讲解和源代码。
  • 本教程文档是 .md 格式,此讲解窗口采用阿里云 CloudShell 的teachme指令打开,如命令行输入 teachme doc/fileName.md 命令打开。
  • CloudShell 默认模式是登录失效后线上机器内信息删除,建议您在本地机器上编辑和保存自己的代码,然后通过 CloudShell 左上角上传文件的方式上传,也可进行下载。CloudShell 窗口关闭后原登录信息会清除,建议同时开两个窗口,防止误操作关闭;同时不建议离开窗口太久导致登录失效。
  • 如果想体验运行MindOpt求解器代码,请①在天池-决策优化MindOpt网址申请免费的授权Token,并替换掉示例代码里的Token;②并安装MindOpt优化求解器的SDK:安装指导。如已安装,可跳过。

^___^ 还没体验过安装和运行求解器的同学,可以直接点击链接:一键安装MindOpt求解器,并一键用令行求解.mps或.lp文件~~

案例问题背景

Flow Shop 是调度领域中的经典模型:

  • 给定一组机器和一批工件,所有工件都按相同顺序依次流过这些机器;
  • 工件在各台机器上的加工时长为给定值,一旦工件进入机器的时长已达相应加工时长,工件立即离开该机器;
  • 在任何时刻,一台机器仅能加工最多一个工件;
  • 优化的目标为最小化makespan,即最后完成所有加工的时间;
  • 决策为确定工件之间的先后顺序。

image.png

该问题可以通过黑盒方法或混合整数规划的方法进行求解,在求解过程中,对某个候选解与理论最优解的距离进行估计,可以帮助我们评估解的质量。为获得下界的估计,我们可以松弛混合整数规划模型中的整数约束,得到一个线性规划,求解该松弛问题,即可得到原问题的一个下界。

Flow Shop 调度的MIP模型及其LP松弛

变量

image.png

目标

image.png

约束

image.png

MIP模型

image.png

LP松弛模型

image.png

Tips:案例内容可能参考自互联网,如有侵权,请联系我们删除。

Flow Shop 调度下界求取:求解LP松弛模型

创建py文件和运行

创建一个.py文件如下(文件夹已创建可删除前几句)。(除示例nano指令外,编辑文件可使用vi、vim、nano、emacs等不同编辑器指令,或touch创建文件,也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行新增和修改。)

mkdir example3
cd example3
nano mindopt_example3.py

复制后文的Python代码,代码框的有上方有复制按钮,然后创建一个文件复制入,并修改代码里面的 line 146 和 line 195 这两处的Token为你自己的Token。

复制后根据提示来修改和保存文件,如ctrl+o保存,然后看到对应名字OK后摁enter即可,如ctrl+x退出,如有修改保存按Y,再看到对应名字OK后摁enter即可退出。

也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行修改。

运行程序可输入以下指令:

python mindopt_example3.py

注:问题提交远端计算Server后,会需要求解时间,请耐心等待。由于计算资源限制,同一Token同时间只能求解一个问题,请勿同时段提交太多次。如果代码运行失败,可能是mindopt环境变量链接失败,可重新走一遍安装步骤(安装指导)。

python 代码

Tips:  如果想体验运行MindOpt求解器代码,请先在天池-决策优化MindOpt-免费使用上申请授权Token,并替换掉示例代码里的Token。

请修改代码里面的 line 146 和 line 195 这两处的Token为你自己的Token。

#! python3

'''
Lower Bound Calculation for Flow Shop Scheduling Optimization
with MindOpt LP Solver

This program builds linear program relaxation (LPR) for the flow shop scheduling
instance ta001 from the Taillard Flow Shop Scheduling Benchmarks, and solve
the LPR with the LP Solver of the MindOpt Optimization Suite.
'''

from mindoptpy import *

##############################
#model data
##############################

#number of machines
M = 5 

#number of jobs
J = 20   

#processing time data from the benchmark:
TA001_Proc_Times = [54,83,15,71,77,36,53,38,27,87,76,91,14,29,12,77,32,87,68,94, \
              79,3,11,99,56,70,99,60,5,56,3,61,73,75,47,14,21,86,5,77, \
              16,89,49,15,89,45,60,23,57,64,7,1,63,41,63,47,26,75,77,40, \
              66,58,31,68,78,91,13,59,49,85,85,9,39,41,56,40,54,77,51,31, \
              58,56,20,85,53,35,53,41,69,13,86,72,8,49,47,87,58,18,68,28]

#data utility function
def processTimeOf(m, j):
    '''
    m: int, index of a machine
    j: int, index of a job
    retrieve the processing time of job j on machine m
    '''
    i = m*J+j                    #the index in the data array
    return TA001_Proc_Times[i]   #the processing of job j at machine m

# the large enough number Z (usually referred to as bigM)
Z = 1.0e7

##############################
#setup and solve the model 
##############################


model_file = './model.mdo'
param_file = './param.mdo'


def ta001_lower_bound():
    '''
    call MindOpt to build and solve the LPR
    '''
    try:
        ###################################
        #step1: initialize MindOpt model 
        model = MdoModel()

        ###########################################
        #step2: build the linear programming model

        #2.1 setup the optimization direction/sense to 'min'
        model.set_int_attr('MinSense', 1)

        #2.2 setup variables
        INF = MdoModel.get_infinity()

        #lowerbound, upperbound, coefficient in objective
        cmax = model.add_var(0.0, INF, 1.0, None, 'Cmax', False)

        s = {}
        for m in range(M):
            for i in range(J):
                sname = 's_%d_%d'%(m,i)
                s[sname] = model.add_var(0.0, INF, 0.0,None,sname,False)

        x = {}
        for i in range(J):
            for j in range(J):
                if i != j:
                    xname = 'x_%d_%d'%(i,j)
                    x[xname] = model.add_var(0.0, 1.0, 0.0, None, xname, False)

        #2.3 setup constraints

        # x_ij + x_ji = 1
        for i in range(J):
            for j in range(J):
                if i<j:
                    cname = 'ExclusiveOrder_%d_%d'%(i,j)
                    expr = MdoExprLinear()
                    expr += x['x_%d_%d'%(i,j)]+ x['x_%d_%d'%(j,i)]
                    model.add_cons(1.0, 1.0, expr, cname)

        # s_mj >= s_mi + P_im + (x_ij -1) Z
        # => s_mi + Z x_ij - s_mj <= Z - P_im
        for m in range(M):
            for i in range(J):
                for j in range(J):
                    if i != j:
                        cname = 'Following_%d_%d_%d'%(m,i,j)
                        expr = MdoExprLinear()
                        expr += s['s_%d_%d'%(m,i)] + Z*x['x_%d_%d'%(i,j)] - s['s_%d_%d'%(m,j)]
                        rub = Z - processTimeOf(m,i) # Z - P_im
                        model.add_cons(-INF, rub, expr, cname)

        #s_(m+1),i >= s_mi + P_mi
        # => s_(m+1)i - s_mi >= P_mi
        for m in range(M-1):
            for i in range(J):
                cname='NextStart_%d_%d'%(m,i)
                proctm = processTimeOf(m,i)
                expr = MdoExprLinear()
                expr += s['s_%d_%d'%(m+1,i)] - s['s_%d_%d'%(m,i)]
                model.add_cons(proctm, INF, expr, cname)


        #cmax >= s_Mi + P_iM
        # => cmax - s_Mi >= P_iM
        for i in range(J):
            m = M-1
            cname = 'Cmax_%d'%(i)
            expr = MdoExprLinear()
            expr += cmax - s['s_%d_%d'%(m,i)]
            proctm = processTimeOf(m,i)
            model.add_cons(proctm, INF, expr, cname)


        #optional step: write to LP file for further use
        model.write_prob('flowshop_ta001.lp')

        ###########################################
        #step 3: Serialize the model and settings for further submission

        model.set_int_param('NumThreads', 4)
        model.set_real_param('MaxTime', 3600.0)

        model.write_task(model_file, True, False, False)
        model.write_task(param_file, False, True, False)

        ############################################
        #step 4: connect remote server and submit the model
        model.set_str_param("Remote/Token", "xxxxxxxxxxxxTokenxxxxxxxx")# change to your token
        model.set_str_param("Remote/Desc", "tianchi example3 FlowShop")
        model.set_str_param("Remote/Server", "mindopt.tianchi.aliyun.com")
        model.set_str_param("Remote/File/Model", model_file)
        model.set_str_param("Remote/File/Param", param_file)

        job_id = model.submit_task()
        if job_id == "":
            print("ERROR: Empty job ID.")
            return None
        else:
            print("Job was submitted to server successfully.")
            print("User may query the optimization result with the following job ID: {}".format(job_id))
            return job_id

    except MdoError as e:
        print("Received Mindopt exception.")
        print(" - Code          : {}".format(e.code))
        print(" - Reason        : {}".format(e.message))
        return None
    except Exception as e:
        print("Received exception.")
        print(" - Reason        : {}".format(e))
        return None
    finally:
        #################################
        # step 5. Free the model.
        model.free_mdl()


def fetch_result(job_id):
    if job_id is None or len(job_id)<1:
        print("Error: bad job id.")
        return

    soln_file = "./my_soln.mdo"
    val = 0.0
    status = "Submitted"
    MDO_INFINITY = MdoModel.get_infinity()
    # Step 1. Create a model and change the parameters.
    model = MdoModel()

    try:        
        # Step 2. Read the serialized model and parameters -- this is 
        #         required while populating the optimization result. 
        model.read_task(model_file, True, False, False)
        model.read_task(param_file, False, True, False)        

        # Step 3. Input parameters related to the remote computing server.
        model.set_str_param("Remote/Token", "xxxxxxxxxxxxTokenxxxxxxxx")# change to your token
        model.set_str_param("Remote/Server", "mindopt.tianchi.aliyun.com")
        model.set_str_param("Remote/File/Soln", soln_file)

        # Step 4. Check the solution status periodically, and             
        #         download the its upon availability.       
        while status == 'Submitted' or status == 'Solving': 
            status, model_status, result, has_soln = model.retrieve_task(job_id)
            # Sleep for 10 seconds.
            time.sleep(10)

        result_details = model.explain_result(result)

        print(" - Job status             : {}".format(status))
        print(" - Optimization status    : {0} ({1})".format(result_details, result))
        print(" - Solution availability  : {0}".format("available" if has_soln else "not available"))

        if has_soln:
            print("\nPopulating solution.")

            model.read_task(soln_file, False, False, True)
            model.display_results()
            print(" - Primal objective value : {}".format(model.get_real_attr("PrimalObjVal")))
            print(" - Dual objective value   : {}".format(model.get_real_attr("DualObjVal")))
            print(" - Solution time          : {} sec.".format(model.get_real_attr("SolutionTime")))
            # write to sol file -- text file showing solution details
            model.write_soln('flowshop.sol')

    except MdoError as e:
        print("Received Mindopt exception.")
        print(" - Code          : {}".format(e.code))
        print(" - Reason        : {}".format(e.message))
    except Exception as e:
        print("Received exception.")
        print(" - Reason        : {}".format(e))
    finally:
        # Step 5. Free the model.
        model.free_mdl()


# the main entrance of the program
if __name__ == '__main__':
    job_id = ta001_lower_bound() 
    if job_id is not None:
        fetch_result(job_id)

求解结果

运行上述代码后结果示例如:

MindOpt Version 0.12.0 (Built: 20201227)
Copyright (c) 2020 Alibaba Cloud.

response_code:200
Returned job ID: 709E49B29ECD4FADC75E038A162C5AE8.
response body: 709E49B29ECD4FADC75E038A162C5AE8 
Job was submitted to server successfully.
User may query the optimization result with the following job ID: 709E49B29ECD4FADC75E038A162C5AE8
MindOpt Version 0.12.0 (Built: 20201227)
Copyright (c) 2020 Alibaba Cloud.

Reader started. File  : ./model.mdo
Reader terminated. Time : 0.001s
Reader started. File  : ./param.mdo
Reader terminated. Time : 0.000s
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100     7  100     7    0     0    241      0 --:--:-- --:--:-- --:--:--   241
response_code:200
Status: PENDING 
str_map_status:Submitted
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100     7  100     7    0     0    184      0 --:--:-- --:--:-- --:--:--   184
response_code:200
Status: OPTIMAL 
str_map_status:Finished
100   149  100   149    0     0   9312      0 --:--:-- --:--:-- --:--:--  9312
response_code:200
Summary:{"code":0,"dual_obj_val":353.0,"has_soln":1,"num_cols":481,"num_ents":6280,"num_rows":2190,"primal_obj_val":353.0,"soln_time":0.046792096,"status":1}
Solver code: 0
has_soln: 1
Writing solution to file <./my_soln.mdo>
100 54384    0 54384    0     0   931k      0 --:--:-- --:--:-- --:--:--  931k
 - Job status             : Finished
 - Optimization status    : Nothing. (0)
 - Solution availability  : available

Populating solution.
Reader started. File  : ./my_soln.mdo
Reader terminated. Time : 0.000s
Optimizer summary.
 - Optimizer used     : Simplex method
 - Optimizer status   : OPTIMAL
 - Total time         : 0.047s

Solution summary.       Primal solution               Dual solution
 - Objective          : 3.5300000000e+02              3.5300000000e+02 
 - Norm               : 3.53e+02                      1.00e+00
 - Var. viol.         : 0.00e+00                      0.00e+00
 - Cons. viol.        : 8.76e-10                      0.00e+00
 - Primal objective value : 353.0
 - Dual objective value   : 353.0
 - Solution time          : 0.046792096 sec.

此输出的结果提示了目标值 353.0。

同时文件夹中生成了 flowshop.sol 文件,里面标了变量的求解值、和目标值 353.0,即根据这个变量的生产计划,可以使得完工时间降低为353.0 。 image.png