Topic
12 replies Latest Post - ‏2013-03-27T21:04:44Z by bgokgur
bgokgur
bgokgur
8 Posts
ACCEPTED ANSWER

Pinned topic Sequence variable in CP Optimizer

‏2013-03-20T08:54:15Z |
Hi all,

I wonder that is there any way to access position member of sequence variable ?

I can access them after solution is obtained. However, I want to use position element of sequence variable while I am writing a constraint.
Thank you for your support,

Burak.
Updated on 2013-03-27T21:04:44Z at 2013-03-27T21:04:44Z by bgokgur
  • rdumeur
    rdumeur
    52 Posts
    ACCEPTED ANSWER

    Re: Sequence variable in CP Optimizer

    ‏2013-03-20T11:09:53Z  in response to bgokgur
    Dear bgokgur,

    There is no direct way to access the position of a sequence var member. But depending on what you wish to do with this positional information, we can advise you on the best way to compute and use it. So, could you please give more details about your model and what is the intended use of sequence member positions?

    Cheers,
    • bgokgur
      bgokgur
      8 Posts
      ACCEPTED ANSWER

      Re: Sequence variable in CP Optimizer

      ‏2013-03-20T12:58:05Z  in response to rdumeur
      Thank you for your reply.

      My problem briefly is:

      There are set of jobs to be processed on parallel machines. For each job, there are set of tools required to be loaded before processing the job. Required set of tools of each job may vary. Also, processing of each job may vary on different machines.

      I just want to write a constraint for each tool such that

      in what sequence it is used and on which machine ? and I want to say that if that tool used on different machines on consecutive positions by jobs, then say a binary variable takes value 1.

      To be able to this, I thought that I need to access position element of sequence variable. In my CP model, tools and machines are unary resources.

      Again, thank you for your help,

      Burak.
      • rdumeur
        rdumeur
        52 Posts
        ACCEPTED ANSWER

        Re: Sequence variable in CP Optimizer

        ‏2013-03-20T16:09:18Z  in response to bgokgur
        Dear bgokgur,

        The model given at the end of the message shows how to use transition costs to model the fact that a tool moves between machines. Basically, you only need to create:
        - job interval vars
        - alternatives for machine usage associated to each job.
        - a noOverlap constraint on a sequence made from these jobs
        - one sequence per tool associated with a transition cost matrix. Each member of this sequence is one of each job/machine alternative member requiring the tool.
        - applying the noOverlap constraint on each sequence with the associated cost matrix will introduce delays between consecutive intervals of the sequence corresponding to the change of tool.
        At the beginning of the constraint declaration ("subject to") a couple of constraints are introduced that force a tool to be moved between two machines, hence introducing a delay between job #1 and job #2. Without them, the optimizer manages to group jobs on machine so that no tool motion is required (and thus no extra delay is introduced).

        I hope this helps.

        Cheers,

        
        
        /********************************************* * OPL 12.5 Model * Author: R_Dumeur * Creation Date: 20 mars 2013 at 14:26:17 *********************************************/ using CP;   tuple JobDurationTuple 
        { string name; 
        
        int duration; 
        };   tuple JobMachineTuple 
        { string job; string machine; 
        }   tuple ToolTransitionCostTuple 
        { string tool; string before; string after; 
        
        int cost; 
        }   tuple JobToolTuple 
        { string job; string tool; 
        } 
        // problem data   
        {string
        } JobSet = 
        { 
        "j1", 
        "j2", 
        "j3", 
        "j4", 
        "j5" 
        }; 
        // { j | <j,d> in JobDurationSet }; 
        {string
        } MachineSet = 
        { 
        "m1", 
        "m2" 
        }; 
        // { m | <j,m> in JobMachineSet };   
        {JobMachineTuple
        } JobMachineSet = 
        { <j,m> | j in JobSet, m in MachineSet 
        }; 
        {JobDurationTuple
        } JobDurationSet = 
        { <j,10> | j in JobSet 
        }; 
        {JobToolTuple
        } JobToolSet = 
        { <
        ", "t1
        ">, <", 
        "t1">, <
        ", "t1
        ">, <",
        "t2">, <
        ","t2
        "> };   
        {ToolTransitionCostTuple
        } ToolTransitionCostSet = 
        { <
        ","m1
        ","m2
        ",10>, <
        ","m2
        ","m1
        ",10> 
        };   
        // entities 
        {string
        } ToolSet = 
        {t | <j,t> in JobToolSet 
        };   
        
        int JobDuration[j in JobSet] = first(
        {d | <j,d> in JobDurationSet 
        }); 
        
        int MachineIndex[m in MachineSet] = ord(MachineSet, m); range MachineIndices = 0..card(MachineSet); dvar interval job[j in JobSet] size JobDuration[j]; dvar interval job_machine[JobSet][MachineSet] optional ; dvar sequence machine_job[m in MachineSet] in all(<j,m> in JobMachineSet) job_machine[j][m]; dvar sequence tool_machine[t in ToolSet] in all(<j,t> in JobToolSet, m in MachineSet) job_machine[j][m] types all(<j,t> in JobToolSet, m in MachineSet) MachineIndex[m]; tuple TransitionCostTuple 
        { 
        
        int m1; 
        
        int m2; 
        
        int value; 
        } 
        {TransitionCostTuple
        } ToolMachineTransitionCost[t in ToolSet] = 
        { <a,b,c> | a,b in MachineIndices, <t,sa,sb,c> in ToolTransitionCostSet : a == MachineIndex[sa] && b == MachineIndex[sb] 
        };   minimize max(j in JobSet) endOf(job[j]);   subject to 
        { 
        // To show transition cost, force presence of job #2 on machine #2 
        // this will force requirement of tool #2 on this machine 
        // and introduce a transition cost. presenceOf(job_machine[
        "j2"][
        "m2"]) == 
        
        true; presenceOf(job_machine[
        "j1"][
        "m1"]) == 
        
        true; endBeforeStart(job[
        "j1"],job[
        "j2"]); forall(j in JobSet) 
        { alternative(job[j], all(<j,m> in JobMachineSet) job_machine[j][m]); 
        } forall(m in MachineSet) 
        { noOverlap(machine_job[m]); 
        } forall(t in ToolSet) 
        { noOverlap(tool_machine[t], ToolMachineTransitionCost[t]); 
        } 
        }
        
        • bgokgur
          bgokgur
          8 Posts
          ACCEPTED ANSWER

          Re: Sequence variable in CP Optimizer

          ‏2013-03-20T20:10:36Z  in response to rdumeur
          dear rdumeur,

          Thanks for your support. I forgot to mention about tool switches in my problem.

          There is also tool switches(independent from jobs and it has constant time) and tool magazine capacity in my problem. A tool switch can occur in two ways:

          1) when a tool is moved to different machines
          2) if the number of required set of tools of two consecutive jobs exceeds tool magazine capacity
          I can't reflect these situations into my model.
          • bgokgur
            bgokgur
            8 Posts
            ACCEPTED ANSWER

            Re: Sequence variable in CP Optimizer

            ‏2013-03-20T20:12:21Z  in response to bgokgur
            Because of tool switches, I want to access position element of sequence variable.

            Again, thank you for your support.
            • rdumeur
              rdumeur
              52 Posts
              ACCEPTED ANSWER

              Re: Sequence variable in CP Optimizer

              ‏2013-03-21T10:03:15Z  in response to bgokgur
              Hi,

              As shown in the attached model, you can model tool changes with transition costs between jobs for a given machine. So, again, you can avoid knowing the position of the interval in a sequence.
              In the attached file, we specify, for the sake of the example, the transition delay between two job to be the absolute value of the difference of the job indices.
              This is done with:
              
              
              {TransitionCostSymbolicTuple
              } JobTransitionCostSet = 
              { <m,j1,j2,c> | m in MachineSet, j1,j2 in JobSet, c in 0..card(JobSet) : c == abs(JobIndex[j1]-JobIndex[j2]) 
              };
              

              We generate the tuple set specifying integer indices required by the noOverlap method:
              
              
              {TransitionCostTuple
              } MachineJobTransitionCost[m in MachineSet] = 
              { <a,b,c> | a,b in JobIndices, <m,sa,sb,c> in JobTransitionCostSet : a == JobIndex[sa] && b == JobIndex[sb] 
              };
              

              And eventually we pass this transition matrix to the noOverlap constraint on the machine_job sequence:
              
              forall(m in MachineSet) 
              { noOverlap(machine_job[m], MachineJobTransitionCost[m]); 
              }
              


              Naturally, you can define any kind of transition delay introduced by the fact that a machine switches from a job to another. It could depend on the number and nature of tools that need to be changed in the machine during two consecutive jobs.

              I hope it helps,

              Cheers,
              • bgokgur
                bgokgur
                8 Posts
                ACCEPTED ANSWER

                Re: Sequence variable in CP Optimizer

                ‏2013-03-21T14:15:15Z  in response to rdumeur
                dear rdumeur,

                That is exactly what I need. I should have thought that I could develop right tuples for transition matrix without trying to access position element of sequence variable.

                Thank you for your support.
            • bgokgur
              bgokgur
              8 Posts
              ACCEPTED ANSWER

              Re: Sequence variable in CP Optimizer

              ‏2013-03-25T20:47:47Z  in response to bgokgur
              dear rdumeur,

              I made a mistake in explaining my problem.

              In 2nd case of tool switching, considering two consecutive jobs whether the number of required set of tools of them exceeds tool magazine capacity will not be enough.

              I have to consider all assigned jobs for each machine.

              For example,
              Assigned jobs for machine 1 -> J1-J5-J4-J6-J10
              Each combination of subset of consecutive jobs must be checked for tool magazine capacity such as
              (J1-J5), (J1-J5-J4), (J1-J5-J4-J6), (J1-J5-J4-J6-J10)

              I first thought that I could generate tuple for each possible combination of jobs sequence but the number of instance of all tuples is too much.

              Is there a more intelligent way to check cumulatively subset of jobs for tool magazine capacity ?

              Thank you for your help,
              Burak.
              • SystemAdmin
                SystemAdmin
                623 Posts
                ACCEPTED ANSWER

                Re: Sequence variable in CP Optimizer

                ‏2013-03-26T13:40:28Z  in response to bgokgur
                Hello,
                I think that you should formalize more what happens when the capacity of the machine magazine is exceeded. What happens then ? Let's assume that if the maximal capacity of the magazine is reached and a new tool needs to be installed on the machine, then at least one of the current tools in the machine magazine needs to be removed (and stored somewhere else) and that this operation will require some time. So if a given tool Ti cannot stay in the machine magazine, it need to be removed from the magazine and will not be able to be available again before some minimal time has elapsed.

                For instance, with your example of sequence on machine 1: J1-J5-J4-J6-J10. If the capacity of the magazine is 2, we have 4 tools T1..T4 and if we have the following tool requirements by jobs: J1:{T1,T2}, J5:{T2,T3}, J4:{T1,T3}, J6:{T3,T4}, J10:{T1,T4}. Let's suppose the jobs are all 10 and that when the magazine capacity is exceeded it requires 30 units of time to install a new tool. A solution could be:

                J1 executes on [0,10) with T1 and T2, magazine usage is 2
                J5 executes on [10,20) with T2 and T3, T1 needs to be removed from the magazine in order not to exceed the capacity so it won't be available until 10+30=40
                J4 executes on [40,50) with T1 (that has been put back in the magazine which explains the delay) and T3 (already in magazine), magazine is full, so T1 needs to be removed again from the magazine in order not to exceed the capacity, it won't be available until 50+30=80
                J6 executes on [50,60) with T3 and T4 (installed in place of T1)
                J10 executes on [80,90) with T1 (that has been put back in the magazine which explains the delay) and T4 (already in magazine)

                You could model this with a model like the one attached. For simplicity, I considered a single machine but it can easily be extended to alternative machines, the only difference will be that the job intervals are optional. The model introduces some additional interval variables (optional interval variables occupyMagazine) to represent the contiguous occupation of the machine magazine by a particular tool. We do not know the number of these intervals a priori (that's why they are optional) but we know their number cannot exceed the number of jobs requiring the tool on the machine and we can break evident symmetries in the problem by adding precedence and implication constraints between these intervals. Then the constraints state that:
                1- during the execution of a job the required tools need to be installed in the magazine (alwaysIn constraint)
                2- there is a minimal delay that must elapse between two consecutive presences of the tool in the magazine (delay in the endBeforeStart constraints)
                The maximal capacity of the magazine is then modeled as a limit on a global cumul function on the machine.

                This model can be adapted if you have a slightly different definition for what happens when the magazine is full. Note also that finding an initial feasible solution may not be trivial for CP Optimizer on this type of model. If constraints on the magazine capacities are not real bottlenecks in your problem, it could be a good idea to first solve the problem with a relaxation or an approximation of this constraint (for instance the relaxation only considering pairs of consecutive jobs) and then, once a solution has been found, re-optimize it by considering those magazine capacities. For that you can use the notion of "starting point" in CP Optimizer.

                Philippe
                • bgokgur
                  bgokgur
                  8 Posts
                  ACCEPTED ANSWER

                  Re: Sequence variable in CP Optimizer

                  ‏2013-03-26T21:16:01Z  in response to SystemAdmin
                  Dear Philippe,

                  First of all, thank you for your help.

                  I did not understand one point in the model that you attached. "Horizon" is defined and optional size of tool interval variable is set to minduration to horizon.

                  What is the reason of defining horizon and setting optional size of tool interval variable such as minduration..Horizon ?

                  Also, I might miss some crucial points in the model but when I check the starting and ending time of jobs in the solution of the model, there is no transition time between jobs even if switching must occurs because of tool magazine capacity between some subset of consecutive jobs.
                  • SystemAdmin
                    SystemAdmin
                    623 Posts
                    ACCEPTED ANSWER

                    Re: Sequence variable in CP Optimizer

                    ‏2013-03-27T08:17:17Z  in response to bgokgur
                    Hello,

                    "Horizon" is not really important in the model. It could be any large value. It is used in the definition of interval variables occupyMagazine to define the domain of the size of the interval. The maximum size ("Horizon") is not really important. what is more important is the minimal size. Interval variable occupyMagazine represents the time interval during which a given tool stays in the magazine of a machine. It would be sufficient to set a minimal size of 1 for such an interval. In the attached model, it is slightly optimized by the fact that if a tool is in the magazine of a machine for performing a job, the duration of such an interval of time will be at least the minimal duration of all jobs requiring this tool on the machine. This is why the min size is stated to be minJobDuration[tj.tool]. As the OPL syntax for defining a min size also requires a value for the max, that's the reason for introducing "Horizon".

                    In the model I attached there is no transition time on the machine beside the tool transition constraint. And a transition between tools does not necessarily imply a transition between consecutive jobs on the machine (but this is because of the interpretation I did of your description of the tool change constraint). Look at the example I gave:

                    For instance, with your example of sequence on machine 1: J1-J5-J4-J6-J10. If the capacity of the magazine is 2, we have 4 tools T1..T4 and if we have the following tool requirements by jobs: J1:{T1,T2}, J5:{T2,T3}, J4:{T1,T3}, J6:{T3,T4}, J10:{T1,T4}. Let's suppose the jobs are all 10 and that when the magazine capacity is exceeded it requires 30 units of time to install a new tool. A solution could be:

                    J1 executes on [0,10) with T1 and T2, magazine usage is 2
                    J5 executes on [10,20) with T2 and T3, T1 needs to be removed from the magazine in order not to exceed the capacity so it won't be available until 10+30=40
                    J4 executes on [40,50) with T1 (that has been put back in the magazine which explains the delay) and T3 (already in magazine), magazine is full, so T1 needs to be removed again from the magazine in order not to exceed the capacity, it won't be available until 50+30=80

                    There is indeed no transition time between the first two jobs J1 and J5. It is because in my interpretation, if the capacity of the magazine is 2, switching from {T1,T2} to {T2,T3} does not require any delay between the jobs: moving T1 out of the magazine can be done in parallel with installing T3. It is only when T1 will have to be re-installed in the magazine that it will require some time, but this re-installation can be done without interrupting the machine, it will only delay the time a new job requiring tool T1 can start (like the subsequent job J4 in the above example).

                    Your question when looking at the solution shows that my interpretation of the tool change constraint is probably not the right one. This is why I asked if you can formalize this tool change constraint so that there is no ambiguity about its possible interpretation. Note that the attached model with cumul function can be adapted to other interpretations of the tool change constraint. The chain of intervals occupyMagazine really represent the set of time intervals during which the tool needs to stay in the machine magazine in order to perform some jobs. You can for instance add addition intervals in the chain of intervals occupyMagazine to represent activities related with tool removal/installation in the machine magazine. These interval variables could require the machine and even, why not, other resources.
                    Philippe
                    • bgokgur
                      bgokgur
                      8 Posts
                      ACCEPTED ANSWER

                      Re: Sequence variable in CP Optimizer

                      ‏2013-03-27T21:04:44Z  in response to SystemAdmin
                      Dear Philippe,

                      I appreciate your help.

                      I understood your point. I will try to make some change by adding some additional interval variables as you mentioned. After that, If I again have any questions, I will post it to here.

                      Thank you,

                      Burak.