Job-shop scheduling problem with machines at different speeds (JSMS)

The traditional scheduling models consider performance indicators such as processing time, cost and quality as optimization objectives. However, most of them do not take into account energy consumption. We focus our attention in a job-shop scheduling problem where machines can work with different energy consumptions. It represents an extension of the classical job-shop scheduling problem, where each operation has to be executed by one machine and this machine can work at different voltage.

Formally the job-shop scheduling problem with machines at different speeds (JSMS) can be defined as follows. We are given a set of n jobs {J1 , . . . , Jn }, a set of m resources or machines {R1 , . . . , Rm }. Each job Ji consists of a sequence of vi tasks (θi1 , . . . , θivi ). Each task θil has a single machine requirement Rθil and a start time stθil to be determined. Each machine can work with different speeds, the duration and energy combination is presented by a tuple {pθil ,eθil } A feasible schedule is a complete assignment of starting times tasks that satisfies the following constraints:

  • 1. The tasks of each job are sequentially scheduled.
  • 2. Each machine can process at most one task at any time.
  • 3. No preemption is allowed.
The objective is finding a feasible schedule that minimizes the completion time of all the tasks and the energy used.

Research Group Artificial Intelligence, Planning & Scheduling

Main areas:

  • Scheduling
  • Planning
  • Energy-Efficency
  • Multi-Objective Optimization
  • Algorithms

Instance Examples

3_5_10 

nbJobs = 3;
nbMchs = 3;
nbOp = 5;

Ops = [
[<1,2>, <2,1>, <3,0>, <4,2>, <5,0>],
[<6,0>, <7,1>, <8,2>, <9,1>, <10,2>],
[<11,0>, <12,2>, <13,1>, <14,0>, <15,2>]
];

Modes = {
<1,14,14>,<1,16,10>,<1,19,7>,
<2,4,6>,<2,5,5>,<2,6,4>,
<3,13,15>,<3,14,11>,<3,15,10>,
<4,3,5>,<4,4,4>,<4,5,3>,
<5,1,4>,<5,2,3>,<5,3,2>,
<6,16,14>,<6,17,12>,<6,18,8>,
<7,5,9>,<7,10,7>,<7,12,6>,
<8,2,4>,<8,3,3>,<8,4,2>,
<9,1,3>,<9,1,2>,<9,2,1>,
<10,1,3>,<10,1,2>,<10,2,1>,
<11,8,9>,<11,12,8>,<11,17,6>,
<12,4,10>,<12,7,7>,<12,13,5>,
<13,1,4>,<13,1,3>,<13,2,2>,
<14,3,10>,<14,5,9>,<14,9,7>,
<15,3,6>,<15,5,4>,<15,6,3>,
};

3_7_100 

nbJobs = 3;
nbMchs = 3;
nbOp = 7;

Ops = [
[<1,1>, <2,0>, <3,1>, <4,0>, <5,2>, <6,0>, <7,2>],
[<8,0>, <9,2>, <10,1>, <11,0>, <12,1>, <13,2>, <14,1>],
[<15,0>, <16,1>, <17,2>, <18,0>, <19,2>, <20,0>, <21,1>]
];

Modes = {
<1,24,74>,<1,40,65>,<1,78,47>,
<2,51,125>,<2,60,91>,<2,113,82>,
<3,114,148>,<3,145,123>,<3,199,94>,
<4,60,110>,<4,102,101>,<4,111,92>,
<5,12,42>,<5,21,33>,<5,30,24>,
<6,75,124>,<6,108,96>,<6,154,87>,
<7,55,98>,<7,109,71>,<7,150,60>,
<8,117,136>,<8,163,117>,<8,175,78>,
<9,26,38>,<9,36,29>,<9,53,20>,
<10,15,47>,<10,26,38>,<10,36,29>,
<11,42,76>,<11,52,55>,<11,78,46>,
<12,26,48>,<12,39,34>,<12,61,23>,
<13,29,44>,<13,46,35>,<13,57,26>,
<14,37,77>,<14,46,68>,<14,69,59>,
<15,65,99>,<15,122,67>,<15,136,54>,
<16,49,96>,<16,58,74>,<16,75,62>,
<17,1,20>,<17,1,11>,<17,2,2>,
<18,35,68>,<18,50,59>,<18,96,44>,
<19,129,116>,<19,158,81>,<19,167,67>,
<20,66,107>,<20,105,94>,<20,155,85>,
<21,81,143>,<21,90,106>,<21,159,84>,
};

7_10_100 

nbJobs = 3;
nbMchs = 7;
nbOp = 10;

Ops = [
[<1,6>, <2,2>, <3,1>, <4,5>, <5,6>, <6,3>, <7,4>, <8,2>, <9,1>, <10,0>],
[<11,4>, <12,1>, <13,4>, <14,0>, <15,6>, <16,4>, <17,1>, <18,5>, <19,6>, <20,1>],
[<21,3>, <22,6>, <23,1>, <24,4>, <25,3>, <26,1>, <27,2>, <28,1>, <29,3>, <30,4>]
];

Modes = {
<1,1,27>,<1,1,17>,<1,8,7>,
<2,1,31>,<2,2,21>,<2,12,11>,
<3,1,34>,<3,8,23>,<3,18,13>,
<4,1,24>,<4,1,14>,<4,7,4>,
<5,35,77>,<5,65,67>,<5,103,48>,
<6,65,52>,<6,75,42>,<6,85,32>,
<7,4,29>,<7,14,19>,<7,24,9>,
<8,23,149>,<8,46,102>,<8,87,84>,
<9,1,22>,<9,1,12>,<9,3,2>,
<10,48,62>,<10,82,52>,<10,92,37>,
<11,49,94>,<11,59,71>,<11,88,61>,
<12,46,151>,<12,87,110>,<12,109,94>,
<13,41,72>,<13,69,62>,<13,133,48>,
<14,62,165>,<14,123,116>,<14,229,89>,
<15,56,168>,<15,92,113>,<15,147,88>,
<16,174,182>,<16,190,130>,<16,200,96>,
<17,1,25>,<17,2,15>,<17,12,5>,
<18,1,27>,<18,1,17>,<18,7,7>,
<19,1,32>,<19,10,22>,<19,20,12>,
<20,20,61>,<20,32,44>,<20,49,33>,
<21,80,70>,<21,90,60>,<21,112,50>,
<22,18,49>,<22,29,39>,<22,39,29>,
<23,97,126>,<23,193,88>,<23,203,72>,
<24,1,23>,<24,1,13>,<24,6,3>,
<25,69,126>,<25,117,98>,<25,153,83>,
<26,42,114>,<26,54,104>,<26,90,78>,
<27,84,96>,<27,118,86>,<27,148,65>,
<28,94,144>,<28,170,134>,<28,228,91>,
<29,17,65>,<29,27,44>,<29,37,34>,
<30,176,127>,<30,190,116>,<30,201,79>,
};


 3_5_10

CP Optimizer Genetic Genetic*+LS
λ Mk En F Mk En F Mk En F
0 71.4 84.4 0.553762 65.8 84.4 0.553762 65.8 84.4 0.553762
0.1 65.2 84.5 0.556581 65.2 84.5 0.556581 65.2 84.5 0.556581
0.2 64.4 84.7 0.558703 64.4 84.7 0.558703 64.4 84.7 0.558703
0.3 63.2 85.2 0.559422 63.2 85.2 0.559422 63.2 85.2 0.559422
0.4 59.7 88.1 0.557816 59.7 88.1 0.557816 59.7 88.1 0.557816
0.5 53.9 94.3 0.547187 54.2 93.9 0.547270 54 94.2 0.547239
0.6 48.4 104.2 0.529935 48.9 103.2 0.529687 49 103 0.529761
0.7 45.3 111.9 0.500419 45 112.7 0.500130 44.8 113.3 0.500084
0.8 42.2 123.4 0.461368 42.2 123.5 0.461509 42.2 123.4 0.461368
0.9 41 133.2 0.414361 41 133.7 0.414712 41 133.2 0.414361
1 41 143.1 0.363050 41 145.3 0.363050 41 152 0.363050































7_10_100

CP Optimizer Genetic Genetic*+LS
λ Mk En F Mk En F Mk En F
0 1088.4 1571.4 0.533616 1006.3 1571.4 0.533616 1006.3 1571.4 0.533616
0.1 999.3 1572.6 0.540932 999.3 1572.6 0.540931 999.3 1572.6 0.540931
0.2 987.2 1576.5 0.547508 987.2 1576.5 0.547509 987.2 1576.5 0.547509
0.3 922.2 1613.3 0.550868 926.9 1610 0.551018 922.2 1613.3 0.550868
0.4 885.9 1649.2 0.550650 891 1642.9 0.550638 888 1646 0.550556
0.5 838.8 1716 0.545249 847.5 1704.8 0.545938 842.1 1711.3 0.545187
0.6 779.1 1859.3 0.535095 782.4 1845.7 0.535361 774.4 1861.1 0.534304
0.7 708.5 2068.4 0.511331 703.9 2099.5 0.512783 704 2085.1 0.511140
0.8 651.8 2346 0.475184 642.4 2418.9 0.475810 644.1 2394.3 0.475081
0.9 626 2560.7 0.428228 626 2573.3 0.428603 626 2560.7 0.428228
1 625.9 2664.1 0.378956 625.9 2773.4 0.378956 625.9 2935.1 0.378956































Watson50

CP Optimizer Genetic Genetic*+LS
λ Mk En F Mk En F Mk En F
0 7648.9 53631.5 0.534084 8359 61290.4 0.610346 7267.5 53631.5 0.534084
0.1 7322.7 53669.5 0.558776 6985.1 63122.2 0.639945 7036.4 53635.2 0.555427
0.2 7258.6 53875 0.583375 6496 64934.4 0.655306 6979.8 53698.9 0.576029
0.3 7192.5 54094.1 0.606205 6121.4 67834.6 0.667899 6945.4 53822.3 0.596453
0.4 7172 54257.6 0.628810 5840.1 71034 0.672533 6824.5 54351.4 0.614622
0.5 7121 54467.3 0.649284 5657.8 73653.8 0.667159 6680.6 55472.4 0.630886
0.6 6552.1 62253.7 0.665704 5559.8 75243.6 0.653968 5305.1 70358 0.618196
0.7 6039.1 71014.7 0.661105 5456.9 76643.2 0.634583 4970.9 75679.6 0.595589
0.8 5947.3 71489.3 0.647691 5466.9 76972.8 0.617737 4896.8 77262.9 0.569877
0.9 5876.3 70699.2 0.632014 5420.4 77869.3 0.595589 4862.8 78307.4 0.542734
1 5008.3 81527.7 0.531812 5396.8 78976.6 0.573094 4265.7 98395.6 0.452947































Watson100

CP Optimizer Genetic Genetic*+LS
λ Mk En F Mk En F Mk En F
0 12671.2 105478.1 0.530618 13763.5 126772.1 0.637760 12339.4 105478.1 0.530617
0.1 12378.1 105513.8 0.561048 11700.8 128923.7 0.662490 12085.9 105483.1 0.558938
0.2 12297.4 105710.8 0.591010 11048 132690.7 0.682760 12074.3 105490.1 0.587106
0.3 12408 105654 0.622653 10347.5 139304 0.699511 11949.3 105921.3 0.614317
0.4 12376.4 105634.3 0.652105 9909.1 144731.7 0.703700 11828.6 106739.4 0.640697
0.5 12097.2 110089.6 0.684038 9769.5 147040.8 0.698713 11573.3 109046.2 0.663841
0.6 10296.9 140905.5 0.699602 9638.4 149638.5 0.690415 8761.3 145892.3 0.647497
0.7 9835.1 150495.9 0.690528 9558.8 151011.4 0.678329 8560.4 150040.1 0.629834
0.8 9785.8 150468.8 0.678396 9524.3 151835.1 0.665705 8406.5 153414.3 0.607110
0.9 9813.2 149937.6 0.669925 9484.8 153036.8 0.651611 8415.8 154301.4 0.587494
1 9434.5 152047.9 0.635030 9511 153336.4 0.640230 7318.7 196574.7 0.492683































Watson200

CP Optimizer Genetic Genetic*+LS
λ Mk En F Mk En F Mk En F
0 22399.6 211041.5 0.530985 23189.1 271449.7 0.682978 21982.7 211040.1 0.530981
0.1 21776 307619.8 0.785615 20317.2 269756.1 0.693916 21725.5 211040.1 0.566732
0.2 21776 307619.8 0.797274 19194.2 279323.8 0.719238 21697.7 211073.5 0.602325
0.3 21776 307619.8 0.808934 18004.6 290852.6 0.733131 21674.5 211331.5 0.638119
0.4 22701.1 279768.9 0.793322 17684.3 294861.1 0.734408 21576.5 211657.1 0.672474
0.5 22428.6 231369 0.749543 17516.5 297864.2 0.732885 21123.5 217626.6 0.705700
0.6 18215.4 282412.4 0.731213 17378.2 299940.4 0.728279 15590.1 297314.6 0.681767
0.7 17439.5 300096.2 0.725809 17341.5 301425.6 0.723949 15311.9 304140.6 0.667889
0.8 17379 300292.6 0.719746 17350 301864.7 0.719531 15277.5 305966.2 0.653797
0.9 17253.8 300856.2 0.710794 17323.3 302255.9 0.713660 15191.8 309181.4 0.636952
1 17074.7 299562.5 0.698323 17295.5 302979 0.707326 13165.5 397436.9 0.538403



PhD. Joan Escamilla Fuster

Email:
jescamilla (_at_) dsic DOT upv DOT es

Address:
Building: Departamento de Sistemas Informáticos y Computación (Edificio 1F). Room: L207
Universitat Politècnica de València.
Camino de Vera s/n,
46022, Valencia, España
Tef. +34 963877000 Ext. 73550
Fax. +34 963877359
Prof. Federico Barber Sanchis

Email:
fbarber (_at_) dsic DOT upv DOT es

Address:
Building: Departamento de Sistemas Informáticos y Computación (Edificio 1F). Room: 2D26
Universitat Politècnica de València.
Camino de Vera s/n,
46022, Valencia, España
Tef. +34 963877000 Ext. 79357
Fax. +34 963877359
Prof. Miguel A. Salido Gregorio

Email:
msalido (_at_) dsic DOT upv DOT es

Address:
Building: Departamento de Sistemas Informáticos y Computación (Edificio 1F). Room: 2D14
Universitat Politècnica de València.
Camino de Vera s/n,
46022, Valencia, España
Tef. +34 963877000 Ext. 83512
Fax. +34 963877359

Downloads

  • Efficiency Energy Instances
  • Type Instances

      Small Instances: All instances have 3 jobs are characterized by the number of machines (m), the maximum number of tasks per job (vmax ) and the range of processing times (pi ). A set of instances were generated combining three values of each parameter: m = 3, 5, 7; vmax = 5, 7, 10 and pi = [1, 10], [1, 50], [1, 100]. In all cases, 10 instances were considered from each combination. The sets of instances are identified by the tuple: < m_vmax _pi >. Each machine can work with different speeds, each speed is linked up to an integer duration pi and an integer energy ei. There are different energy consumptions (e1 , e2 , e3 ) to each task according to three processing times (pt1 , pt2 , pt3 )

      Large Instances: All instances have 3 jobs are characterized the maximum number of tasks per job (vmax ) and the range of processing times (pi ). A set of instances were generated combining three values of each parameter: vmax = 20, 25, 30 and pi = [1, 50], [1, 100], [1, 200]. In all cases, 10 instances were considered from each combination. The sets of instances are identified by the tuple: < m_vmax _pi >. Each machine can work with different speeds, each speed is linked up to an integer duration pi and an integer energy ei. There are different energy consumptions (e1 , e2 , e3 ) to each task according to three processing times (pt1 , pt2 , pt3 )

      Watson Instances: Instances have 50, 100 or 200 jobs, 20 machines and 20 is the maximum number of tasks per job (vmax ). The range of processing times (pi ) is random selected between [1, 100]. In all cases, 10 instances were considered from each combination. The sets of instances are identified by the tuple: < m_vmax _pi >. Each machine can work with different speeds, each speed is linked up to an integer duration pi and an integer energy ei. There are different energy consumptions (e1 , e2 , e3 ) to each task according to three processing times (pt1 , pt2 , pt3 )

      Lawrence Instances: Instances have 10, 15, 20 or 30 jobs, the maximum number of tasks per job (vmax) can be 5, 10 or 15 and the number of machines is equal to the number of tasks. The range of processing times (pi ) is random selected between [1, 100]. In all cases, 5 instances were considered from each combination. The sets of instances are identified by the tuple: < m_vmax _pi >. Each machine can work with different speeds, each speed is linked up to an integer duration pi and an integer energy ei. There are different energy consumptions (e1 , e2 , e3 ) to each task according to three processing times (pt1 , pt2 , pt3 )

      Taillard Instances: Instances have 50 or 100 jobs, the maximum number of tasks per job (vmax) is 20 and the number of machines is equal to the number of tasks. The range of processing times (pi ) is random selected between [1, 100]. In all cases, 10 instances were considered from each combination. The sets of instances are identified by the tuple: < m_vmax _pi >. Each machine can work with different speeds, each speed is linked up to an integer duration pi and an integer energy ei. There are different energy consumptions (e1 , e2 , e3 ) to each task according to three processing times (pt1 , pt2 , pt3 )


  • Structure Instance
  • JSMS Model for CP Optimizer
  • Maximum makespan for instances:
    • Small: 3_5_10 and 7_10_100
    • Large: 3_25_100
    • Watson: 50, 100 and 200
    • Lawrence: 10x5, 15x5, 20x5, 10x10, 15x10, 20x10, 30x10 and 15x15
    • Taillard: 50 and 100

    *These values are the maximum makespan attained in a genetic algorithm execution when λ value is equal to 0. It is used to normalized the objective function. More information in References section in paper "A Metaheuristic Technique for Energy-Efficiency in Job-Shop Scheduling"

  • . . In , In , , (), ed., , (). DOI: