Decision Optimization

Expand all | Collapse all

multiple transition-matrix on the same sequence

  • 1.  multiple transition-matrix on the same sequence

    Posted 3 days ago
    Edited by Andy Ham 3 days ago
    Suppose each job is characterized by group and location. Now, we need to prohibit transitions between groups and penalize transitions between locations. How can I consider two different transitional matrices in the same sequence?
    I created a dummy sequence to consider the second transition matrix. It works, but not efficient for a large-scale instance (50 machines; 10000 jobs). Is there other way? Thanks!

    using CP;

    tuple t_Job {
    key int j;
    int sz;
    int grp;
    int loc;
    } {t_Job} Jobs = {
    <1, 1, 100, 80>,
    <2, 2, 100, 40>,
    <3, 3, 100, 80>,
    <4, 4, 200, 40>,
    <5, 5, 200, 40>,
    <6, 6, 200, 80>,
    <7, 7, 200, 40>,
    <8, 8, 300, 80>,
    <9, 9, 300, 40>,
    <10,10,300, 80>};

    tuple t_forbid_g2g {
    key int g1;
    key int g2;
    int d;
    } {t_forbid_g2g} forbid_g2g = {
    <100, 200, 99999>,
    <100, 300, 99999>};


    tuple t_penalty_l2l {
    key int l1;
    key int l2;
    int d;
    } {t_penalty_l2l} penalty_l2l = {
    <80, 40, 30>,
    <40, 80, 30>};


    dvar interval itvj[j in Jobs] size j.sz;

    dvar sequence seqMch
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.loc;
    //types all(j in Jobs) j.grp;
    minimize max(j in Jobs)endOf(itvj[j]);
    subject to {
    noOverlap(seqMch,forbid_g2g,true);
    //noOverlap(seqMch,penalty_l2l,true);
    }

    /*
    //create dummy sequence to consider the second transition matrix
    using CP;

    tuple t_Job {
    key int j;
    int sz;
    int grp;
    int loc;
    } {t_Job} Jobs = {
    <1, 1, 100, 80>,
    <2, 2, 100, 40>,
    <3, 3, 100, 80>,
    <4, 4, 200, 40>,
    <5, 5, 200, 40>,
    <6, 6, 200, 80>,
    <7, 7, 200, 40>,
    <8, 8, 300, 80>,
    <9, 9, 300, 40>,
    <10,10,300, 80>};

    tuple t_forbid_g2g {
    key int g1;
    key int g2;
    int d;
    } {t_forbid_g2g} forbid_g2g = {
    <100, 200, 99999>,
    <100, 300, 99999>};


    tuple t_penalty_l2l {
    key int l1;
    key int l2;
    int d;
    } {t_penalty_l2l} penalty_l2l = {
    <80, 40, 30>,
    <40, 80, 30>};


    dvar interval itvj[j in Jobs] size j.sz;

    dvar sequence Mch
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.loc;

    dvar sequence MchDummy
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.grp;

    minimize max(j in Jobs)endOf(itvj[j]);
    subject to {
    noOverlap(Mch, penalty_l2l,true);
    noOverlap(MchDummy,forbid_g2g ,true);
    }
    */

    ------------------------------
    Andy Ham
    ------------------------------


  • 2.  RE: multiple transition-matrix on the same sequence

    Posted 3 days ago
    Hi,
    have you tried typeOfNext ?
    regards

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 3.  RE: multiple transition-matrix on the same sequence

    Posted 3 days ago
    I believe we can tag an interval with one "type" on the sequence. So, "typeOfNext" does not provide me a solution since I need to tag an interval with two different "types".
    However, I am using "typeOfNext" in behalf of "transition matrix" since the former delivers a faster performance for my large scale instances.


    ------------------------------
    Andy Ham
    ------------------------------



  • 4.  RE: multiple transition-matrix on the same sequence

    Posted 3 days ago
    Hi,

    so on top of typeOfNext vs noOverlap, you could use several sequences with the same intervals.

    regards

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 5.  RE: multiple transition-matrix on the same sequence

    Posted 2 days ago

    I did create a dummy sequence to consider the second transition matrix. Please see the following code. It works well, but not efficient for a large scale instance (50 machines; 2000 jobs).  The particular test instance has a huge number of forbidden transitions. Better way to model, please? Thanks!


    dvar sequence Mch in all(j in Jobs) itvj[j] types all(j in Jobs) j.loc;
    dvar sequence MchDummy in all(j in Jobs) itvj[j] types all(j in Jobs) j.grp;

    noOverlap(Mch, penalty_l2l,true);
    noOverlap(MchDummy,forbid_g2g ,true);



    ------------------------------
    Andy Ham
    ------------------------------