In one [1], the following problem is sketched:
- We have different types of workers. In the data set below, I call them type-A and type-B workers.
- We need to assign workers to jobs.
- We have more workers than jobs, so we can execute all jobs.
- This is a standard assignment problem: \[\begin{align} \min &\sum_{w,j} \color{darkblue}c_{w,j} \color{darkred}x_{w,j}\\ & \sum_j \color{darkred}x_{w,j} \le 1 &&\forall w \\ & \sum_w \color{darkred}x_{w,j} = 1 && \forall j \\ & \color{darkred}x_{w,j} \in [0,1] \end{align}\]
- The complication is that we can form teams of two workers, one of type A and one of type B. Such a team can work faster and execute the job in less time.
- How to handle this?
I don't know how to handle this within an assignment problem, but stating this as a MIP allows us to make some progress. Allowing two persons to work on a job is easy. Just replace the second constraint by \[1 \le \sum_w \color{darkred}x_{w,j} \le 2\] Unfortunately this ignores that we need one worker of each type in a team. Also, this makes it difficult to impose a cost for each specific team.
As an alternative one could explicitly use teams in the model. Here is my data set with random costs:
---- 13 SET i workers+teams a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10 b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 , b9 , b10 team1 , team2 , team3 , team4 , team5 , team6 , team7 , team8 , team9 , team10 team11 , team12 , team13 , team14 , team15 , team16 , team17 , team18 , team19 , team20 team21 , team22 , team23 , team24 , team25 , team26 , team27 , team28 , team29 , team30 team31 , team32 , team33 , team34 , team35 , team36 , team37 , team38 , team39 , team40 team41 , team42 , team43 , team44 , team45 , team46 , team47 , team48 , team49 , team50 team51 , team52 , team53 , team54 , team55 , team56 , team57 , team58 , team59 , team60 team61 , team62 , team63 , team64 , team65 , team66 , team67 , team68 , team69 , team70 team71 , team72 , team73 , team74 , team75 , team76 , team77 , team78 , team79 , team80 team81 , team82 , team83 , team84 , team85 , team86 , team87 , team88 , team89 , team90 team91 , team92 , team93 , team94 , team95 , team96 , team97 , team98 , team99 , team100 ---- 13 SET w workers a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10, b1 , b2 , b3 , b4 , b5 b6 , b7 , b8 , b9 , b10 ---- 13 SET a type-A workers a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10 ---- 13 SET b type-B workers b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 , b9 , b10 ---- 13 SET t teams team1 , team2 , team3 , team4 , team5 , team6 , team7 , team8 , team9 , team10 team11 , team12 , team13 , team14 , team15 , team16 , team17 , team18 , team19 , team20 team21 , team22 , team23 , team24 , team25 , team26 , team27 , team28 , team29 , team30 team31 , team32 , team33 , team34 , team35 , team36 , team37 , team38 , team39 , team40 team41 , team42 , team43 , team44 , team45 , team46 , team47 , team48 , team49 , team50 team51 , team52 , team53 , team54 , team55 , team56 , team57 , team58 , team59 , team60 team61 , team62 , team63 , team64 , team65 , team66 , team67 , team68 , team69 , team70 team71 , team72 , team73 , team74 , team75 , team76 , team77 , team78 , team79 , team80 team81 , team82 , team83 , team84 , team85 , team86 , team87 , team88 , team89 , team90 team91 , team92 , team93 , team94 , team95 , team96 , team97 , team98 , team99 , team100 ---- 13 SET j jobs job1 , job2 , job3 , job4 , job5 , job6 , job7 , job8 , job9 , job10, job11, job12 job13, job14, job15 ---- 23 SET team composition of teams team1 .a1 , team1 .b1 , team2 .a1 , team2 .b2 , team3 .a1 , team3 .b3 , team4 .a1 team4 .b4 , team5 .a1 , team5 .b5 , team6 .a1 , team6 .b6 , team7 .a1 , team7 .b7 team8 .a1 , team8 .b8 , team9 .a1 , team9 .b9 , team10 .a1 , team10 .b10, team11 .a2 team11 .b1 , team12 .a2 , team12 .b2 , team13 .a2 , team13 .b3 , team14 .a2 , team14 .b4 team15 .a2 , team15 .b5 , team16 .a2 , team16 .b6 , team17 .a2 , team17 .b7 , team18 .a2 team18 .b8 , team19 .a2 , team19 .b9 , team20 .a2 , team20 .b10, team21 .a3 , team21 .b1 team22 .a3 , team22 .b2 , team23 .a3 , team23 .b3 , team24 .a3 , team24 .b4 , team25 .a3 team25 .b5 , team26 .a3 , team26 .b6 , team27 .a3 , team27 .b7 , team28 .a3 , team28 .b8 team29 .a3 , team29 .b9 , team30 .a3 , team30 .b10, team31 .a4 , team31 .b1 , team32 .a4 team32 .b2 , team33 .a4 , team33 .b3 , team34 .a4 , team34 .b4 , team35 .a4 , team35 .b5 team36 .a4 , team36 .b6 , team37 .a4 , team37 .b7 , team38 .a4 , team38 .b8 , team39 .a4 team39 .b9 , team40 .a4 , team40 .b10, team41 .a5 , team41 .b1 , team42 .a5 , team42 .b2 team43 .a5 , team43 .b3 , team44 .a5 , team44 .b4 , team45 .a5 , team45 .b5 , team46 .a5 team46 .b6 , team47 .a5 , team47 .b7 , team48 .a5 , team48 .b8 , team49 .a5 , team49 .b9 team50 .a5 , team50 .b10, team51 .a6 , team51 .b1 , team52 .a6 , team52 .b2 , team53 .a6 team53 .b3 , team54 .a6 , team54 .b4 , team55 .a6 , team55 .b5 , team56 .a6 , team56 .b6 team57 .a6 , team57 .b7 , team58 .a6 , team58 .b8 , team59 .a6 , team59 .b9 , team60 .a6 team60 .b10, team61 .a7 , team61 .b1 , team62 .a7 , team62 .b2 , team63 .a7 , team63 .b3 team64 .a7 , team64 .b4 , team65 .a7 , team65 .b5 , team66 .a7 , team66 .b6 , team67 .a7 team67 .b7 , team68 .a7 , team68 .b8 , team69 .a7 , team69 .b9 , team70 .a7 , team70 .b10 team71 .a8 , team71 .b1 , team72 .a8 , team72 .b2 , team73 .a8 , team73 .b3 , team74 .a8 team74 .b4 , team75 .a8 , team75 .b5 , team76 .a8 , team76 .b6 , team77 .a8 , team77 .b7 team78 .a8 , team78 .b8 , team79 .a8 , team79 .b9 , team80 .a8 , team80 .b10, team81 .a9 team81 .b1 , team82 .a9 , team82 .b2 , team83 .a9 , team83 .b3 , team84 .a9 , team84 .b4 team85 .a9 , team85 .b5 , team86 .a9 , team86 .b6 , team87 .a9 , team87 .b7 , team88 .a9 team88 .b8 , team89 .a9 , team89 .b9 , team90 .a9 , team90 .b10, team91 .a10, team91 .b1 team92 .a10, team92 .b2 , team93 .a10, team93 .b3 , team94 .a10, team94 .b4 , team95 .a10 team95 .b5 , team96 .a10, team96 .b6 , team97 .a10, team97 .b7 , team98 .a10, team98 .b8 team99 .a10, team99 .b9 , team100.a10, team100.b10 ---- 28 PARAMETER c cost coefficients job1 job2 job3 job4 job5 job6 job7 job8 job9 a1 17.175 84.327 55.038 30.114 29.221 22.405 34.983 85.627 6.711 a2 63.972 15.952 25.008 66.893 43.536 35.970 35.144 13.149 15.010 a3 11.049 50.238 16.017 87.246 26.511 28.581 59.396 72.272 62.825 a4 18.210 64.573 56.075 76.996 29.781 66.111 75.582 62.745 28.386 a5 7.277 17.566 52.563 75.021 17.812 3.414 58.513 62.123 38.936 a6 78.340 30.003 12.548 74.887 6.923 20.202 0.507 26.961 49.985 a7 99.360 36.990 37.289 77.198 39.668 91.310 11.958 73.548 5.542 a8 22.575 39.612 27.601 15.237 93.632 42.266 13.466 38.606 37.463 a9 10.169 38.389 32.409 19.213 11.237 59.656 51.145 4.507 78.310 a10 50.659 15.925 65.689 52.388 12.440 98.672 22.812 67.565 77.678 b1 73.497 8.544 15.035 43.419 18.694 69.269 76.297 15.481 38.938 b2 8.712 54.040 12.686 73.400 11.323 48.835 79.560 49.205 53.356 b3 2.463 17.782 6.132 1.664 83.565 60.166 2.702 19.609 95.071 b4 39.334 80.546 54.099 39.072 55.782 93.276 34.877 0.829 94.884 b5 58.032 16.642 64.336 34.431 91.233 90.006 1.626 36.863 66.438 b6 49.662 4.493 77.370 53.297 74.677 72.005 63.160 11.492 97.116 b7 79.070 61.022 5.431 48.518 5.255 69.858 19.478 22.603 81.364 b8 81.953 86.041 21.269 45.679 3.836 32.300 43.988 31.533 13.477 b9 6.441 41.460 34.161 46.829 64.267 64.358 33.761 10.082 90.583 b10 40.419 11.167 75.113 80.340 2.366 48.088 27.859 90.161 1.759 team1 50.421 83.126 60.214 8.225 57.776 59.318 68.377 15.877 33.178 team2 57.624 71.983 68.373 1.985 83.980 71.005 15.551 61.071 66.155 team3 1.252 1.017 95.203 97.668 96.632 85.628 14.161 4.973 55.303 team4 34.968 11.734 58.598 44.553 41.232 91.451 21.378 22.417 54.233 team5 31.014 4.020 82.117 23.096 41.003 30.258 44.492 71.600 59.315 team6 68.639 67.463 33.213 75.994 17.678 68.248 67.299 83.121 51.517 team7 8.469 57.216 2.206 74.204 90.510 56.082 47.283 71.756 51.301 team8 96.552 95.789 89.923 32.755 45.710 59.618 87.862 17.067 63.360 team9 33.626 58.864 57.439 54.342 57.816 97.722 32.147 76.297 96.251 team10 27.016 75.848 61.743 29.100 74.070 0.776 86.651 1.514 42.828 team11 93.347 46.928 21.361 51.078 36.572 93.540 6.801 50.387 39.241 team12 54.748 5.827 37.772 97.407 37.982 15.629 47.226 39.700 20.552 team13 7.212 76.065 29.015 24.495 43.598 36.881 55.342 7.466 90.944 team14 86.568 97.532 57.238 31.397 45.503 37.102 41.985 8.530 81.454 team15 44.431 69.547 67.669 57.154 17.352 60.435 58.599 72.778 24.623 team16 99.602 46.449 53.049 19.038 19.906 64.490 79.908 58.636 97.157 team17 0.309 61.802 0.666 40.558 65.629 61.550 26.341 7.045 4.597 team18 35.535 33.787 48.649 25.937 89.119 84.933 63.452 98.647 75.792 team19 60.358 97.705 55.407 93.504 41.320 80.645 0.078 45.526 41.917 team20 18.987 42.806 16.651 88.626 67.654 86.334 9.276 99.648 61.681 team21 44.199 65.906 48.445 31.819 91.404 18.423 87.211 45.610 45.892 team22 82.294 48.052 91.376 92.928 10.811 35.060 85.998 34.050 21.309 team23 29.676 11.550 39.978 91.176 25.155 10.298 14.633 38.630 4.641 team24 97.215 24.343 36.197 63.034 24.285 10.106 40.593 47.906 14.495 team25 72.042 87.195 29.952 75.390 84.376 46.823 65.493 37.805 35.887 team26 80.649 73.261 92.001 33.164 20.978 4.715 88.304 9.281 83.691 team27 57.996 96.211 51.419 59.030 56.746 2.990 96.890 59.375 5.962 team28 99.295 5.533 61.908 80.444 29.659 95.892 69.475 63.141 61.598 team29 35.582 76.108 13.636 71.663 96.370 44.192 26.448 44.418 39.670 team30 6.910 93.857 84.397 95.044 57.938 3.522 40.743 5.743 53.197 team31 18.614 50.068 93.882 68.157 18.523 87.288 16.501 43.083 77.173 team32 74.914 64.760 74.838 52.317 68.611 69.107 86.565 79.576 21.755 team33 32.482 39.012 29.932 21.896 82.172 15.266 95.055 3.192 73.446 team34 97.108 9.633 47.892 72.217 43.320 15.818 10.066 80.551 39.869 team35 90.918 72.309 16.635 32.755 58.135 57.754 62.758 2.673 12.942 team36 33.861 22.424 90.003 82.938 31.622 95.222 25.669 62.612 97.126 team37 59.518 60.638 63.365 95.824 8.226 12.537 60.522 74.148 84.752 team38 34.621 40.959 93.986 60.293 89.954 28.473 22.224 57.484 50.950 team39 75.582 47.491 7.619 9.750 32.967 20.061 9.075 44.877 46.281 team40 70.315 87.492 55.513 25.563 25.918 35.512 13.688 80.707 32.598 team41 40.712 16.162 86.175 37.771 88.861 26.998 77.739 42.279 42.985 team42 96.851 27.002 31.815 88.338 58.622 38.209 97.298 67.083 95.115 team43 11.834 96.538 84.355 72.133 96.444 36.457 76.831 33.248 54.208 team44 69.156 5.474 24.020 88.275 10.058 67.836 10.138 4.281 75.345 team45 18.595 79.016 86.452 74.793 38.949 79.504 62.098 76.137 58.026 team46 12.291 61.786 53.395 14.408 39.228 1.476 87.077 24.552 80.318 team47 3.952 91.293 54.250 22.099 92.557 79.278 73.938 67.774 50.119 team48 84.202 65.738 11.651 27.425 8.316 50.531 23.268 79.857 98.805 team49 34.050 25.641 99.307 24.779 12.148 94.371 25.320 36.335 39.410 team50 91.418 19.241 14.414 76.037 33.058 0.019 54.343 53.506 86.860 team51 34.192 86.537 46.085 42.106 72.583 66.959 9.290 52.659 89.543 team52 51.518 2.499 44.818 50.129 68.119 79.904 87.295 28.298 91.049 team53 1.814 46.041 62.397 71.636 33.516 1.288 35.621 36.817 91.687 team54 91.703 3.812 30.238 7.003 46.649 56.070 46.509 54.733 17.797 team55 70.710 8.983 40.810 13.683 73.463 59.277 35.746 7.368 63.081 team56 64.880 12.222 76.004 63.311 82.901 90.882 85.856 96.624 3.575 team57 28.704 68.662 27.527 39.028 9.470 21.756 84.353 84.226 88.356 team58 57.295 33.574 39.984 52.038 21.880 70.111 35.389 30.443 95.367 team59 13.348 76.050 9.416 44.537 79.383 46.261 32.450 35.389 17.424 team60 60.266 29.786 50.115 48.842 78.452 62.111 60.558 80.206 65.321 team61 48.293 25.076 48.480 80.988 51.944 97.473 10.245 46.995 1.720 team62 55.262 88.315 57.951 78.826 11.309 65.844 6.641 89.806 88.661 team63 83.952 92.298 23.661 44.994 27.202 5.529 96.659 1.775 1.772 team64 40.231 90.447 44.817 34.879 50.561 39.529 5.694 71.671 17.966 team65 18.090 63.984 14.545 66.332 13.193 70.742 57.057 3.341 28.519 team66 89.692 86.518 54.621 32.159 96.335 91.053 8.301 63.871 7.836 team67 70.988 39.985 21.743 79.525 72.178 78.875 42.399 88.496 65.532 team68 28.220 39.850 65.030 28.160 73.649 66.889 48.940 35.909 67.851 team69 15.372 12.775 86.772 76.504 57.896 78.856 89.680 43.896 58.892 team70 9.648 25.858 13.713 29.323 59.717 68.814 54.855 16.832 81.477 team71 19.761 71.657 31.438 62.191 47.632 79.540 52.101 47.061 61.375 team72 70.554 57.888 27.608 3.980 26.706 23.417 69.728 96.838 67.951 team73 25.746 47.557 87.610 40.229 8.167 70.932 85.333 29.275 27.718 team74 12.422 19.260 68.593 79.726 65.104 46.900 52.869 51.100 40.703 team75 21.644 73.245 57.380 17.480 22.512 98.857 8.098 71.535 71.020 team76 63.699 0.915 41.984 51.118 77.637 69.816 58.570 56.036 62.796 team77 25.208 80.883 81.776 17.895 87.611 4.852 36.311 68.449 71.587 team78 7.306 77.867 62.608 17.979 70.584 44.212 6.017 52.787 41.516 team79 90.690 37.166 86.201 41.745 28.674 18.114 61.104 74.749 84.652 team80 5.566 19.271 6.217 4.931 2.812 59.614 52.066 45.392 93.225 team81 10.011 12.271 56.491 66.269 86.984 72.970 70.643 51.238 66.539 team82 51.279 36.202 94.217 85.481 82.929 5.236 92.337 6.478 48.276 team83 30.503 56.251 38.438 16.202 68.007 28.049 4.744 21.577 75.036 team84 87.864 27.182 14.756 18.279 1.906 64.281 73.222 56.717 57.004 team85 73.607 79.475 4.997 40.372 4.539 37.561 8.753 26.090 45.468 team86 2.424 32.723 54.412 2.884 1.616 42.871 69.679 29.672 70.529 team87 41.065 31.774 50.934 23.799 26.394 69.386 9.290 13.320 10.917 team88 65.125 28.141 11.859 29.774 48.321 25.058 28.436 81.414 80.148 team89 72.420 84.144 67.924 74.009 52.949 38.862 29.610 93.236 81.799 team90 40.964 5.398 56.449 13.812 42.358 54.718 37.845 56.767 72.899 team91 29.231 21.862 51.143 69.911 56.027 33.616 51.876 24.922 41.096 team92 66.764 7.579 41.141 51.840 0.690 18.665 18.361 54.365 55.272 team93 36.443 60.224 83.947 68.479 88.239 61.747 9.943 38.910 2.983 team94 6.396 12.787 28.332 91.485 84.993 21.966 26.917 46.702 51.649 team95 29.600 62.579 93.929 79.012 34.292 58.557 60.675 25.588 3.830 team96 96.945 57.303 8.341 34.519 89.812 54.275 40.901 32.755 98.966 team97 5.720 76.327 87.034 78.061 17.198 69.229 63.387 61.913 0.038 team98 21.277 8.252 28.341 97.284 47.146 22.196 56.537 89.966 15.708 team99 77.385 12.015 78.861 79.375 83.146 11.379 3.413 72.925 88.689 team100 11.050 20.276 21.448 27.928 15.073 76.671 91.574 94.498 7.094 + job10 job11 job12 job13 job14 job15 a1 50.021 99.812 57.873 99.113 76.225 13.069 a2 58.911 83.089 23.082 66.573 77.586 30.366 a3 46.380 41.331 11.770 31.421 4.655 33.855 a4 8.642 10.251 64.125 54.531 3.152 79.236 a5 35.871 24.303 24.642 13.050 93.345 37.994 a6 15.129 17.417 33.064 31.691 32.209 96.398 a7 57.630 5.141 0.601 40.123 51.988 62.888 a8 26.848 94.837 18.894 29.751 7.455 40.135 a9 94.575 59.646 60.734 36.251 59.407 67.985 a10 93.245 20.124 29.714 19.723 24.635 64.648 b1 69.543 84.581 61.272 97.597 2.689 18.745 b2 1.062 54.387 45.113 97.533 18.385 16.353 b3 33.554 59.426 25.919 64.063 15.525 46.002 b4 57.192 33.363 98.375 76.646 11.009 99.480 b5 59.338 3.457 84.182 93.208 50.796 29.960 b6 70.674 98.627 85.482 62.144 70.131 70.089 b7 99.173 75.067 71.834 0.059 26.386 82.382 b8 81.096 41.679 14.178 46.553 28.299 89.568 b9 21.735 91.887 45.175 8.993 37.420 41.499 b10 68.104 95.091 90.018 89.880 87.446 39.100 team1 31.586 51.993 36.379 16.776 68.309 50.539 team2 19.437 36.352 62.390 73.139 41.397 15.749 team3 18.403 99.417 80.909 30.621 8.740 43.050 team4 63.106 32.743 14.878 92.915 25.103 6.259 team5 13.119 16.125 31.563 57.206 26.872 3.639 team6 28.303 55.542 41.399 7.341 80.601 33.272 team7 88.708 77.152 14.012 26.452 68.256 44.980 team8 77.159 56.945 2.768 81.099 27.893 43.335 team9 94.899 25.589 32.495 21.479 17.396 73.125 team10 35.865 70.487 41.587 54.980 34.504 69.958 team11 20.485 52.955 58.909 34.580 25.288 54.766 team12 62.734 0.355 50.395 0.223 52.137 83.612 team13 4.870 82.036 79.295 65.954 39.177 41.315 team14 50.920 73.442 82.438 41.453 92.443 39.415 team15 14.208 89.119 44.276 11.432 90.362 33.385 team16 49.109 37.254 82.717 82.087 3.134 92.520 team17 16.027 45.248 16.887 57.160 85.871 3.587 team18 50.788 76.777 83.213 58.394 57.506 55.671 team19 1.566 8.198 59.881 55.518 61.800 88.509 team20 0.077 60.894 17.371 31.119 72.888 8.475 team21 12.410 10.380 23.489 34.016 87.307 84.479 team22 92.636 36.073 87.599 14.814 45.598 26.825 team23 2.638 15.400 7.271 82.864 39.977 41.717 team24 50.969 88.528 5.548 50.740 76.411 97.900 team25 25.448 25.548 45.062 94.485 33.553 4.849 team26 46.381 0.017 15.658 70.503 28.035 63.558 team27 54.411 12.736 42.049 88.145 71.659 31.358 team28 52.302 14.103 83.673 89.209 69.647 31.179 team29 36.692 62.126 85.973 75.501 90.081 43.805 team30 11.241 89.385 24.169 64.224 29.078 81.356 team31 97.805 94.446 24.884 88.646 88.443 96.495 team32 58.962 92.262 60.290 3.570 91.112 56.501 team33 11.049 48.775 36.104 21.639 92.371 44.996 team34 11.709 87.435 14.486 17.774 54.520 46.860 team35 6.413 31.110 57.851 80.980 67.920 73.567 team36 96.208 42.528 10.539 7.708 64.413 31.222 team37 35.246 64.141 89.573 38.817 27.340 97.040 team38 55.748 34.417 39.827 77.623 2.823 36.238 team39 81.196 45.000 95.426 12.264 40.660 88.637 team40 42.884 0.896 22.429 66.067 28.740 13.112 team41 24.907 38.177 7.098 71.563 70.290 7.016 team42 71.826 44.360 87.973 46.981 46.385 37.143 team43 13.844 31.367 7.988 93.415 49.425 67.891 team44 98.704 1.484 14.686 99.098 13.219 8.543 team45 66.356 8.214 56.686 44.323 32.825 33.060 team46 8.403 98.722 55.827 68.192 85.958 58.673 team47 43.112 57.008 11.104 98.701 51.940 70.649 team48 32.505 85.537 78.998 32.109 21.287 52.089 team49 83.634 44.400 92.630 47.921 90.388 50.953 team50 45.454 35.833 11.389 66.954 93.801 1.507 team51 99.013 50.686 64.450 76.030 90.608 16.629 team52 45.086 87.401 21.689 8.013 70.529 90.050 team53 99.013 20.769 35.039 48.676 64.386 5.633 team54 38.196 51.292 95.655 60.229 45.482 69.008 team55 77.601 42.048 80.743 60.465 65.903 79.763 team56 96.249 0.307 11.849 75.860 25.550 91.410 team57 15.025 75.074 52.294 27.738 62.185 96.519 team58 20.167 92.258 46.872 80.252 33.477 8.141 team59 98.775 12.936 14.749 65.759 16.316 81.181 team60 45.928 59.696 97.952 18.544 98.218 95.787 team61 30.616 30.093 28.045 43.326 50.263 20.108 team62 73.263 62.787 36.521 3.721 72.866 61.417 team63 14.849 47.073 72.492 16.541 8.858 26.414 team64 62.309 40.152 11.728 72.430 71.573 7.407 team65 40.583 83.084 9.441 15.552 90.330 45.777 team66 33.257 10.303 25.409 74.720 9.085 59.351 team67 76.152 20.123 35.185 56.502 76.928 71.735 team68 34.541 56.673 80.032 22.247 42.671 68.199 team69 83.586 42.060 6.977 2.520 85.098 34.960 team70 55.371 44.282 16.569 52.015 82.687 4.228 team71 81.404 82.443 50.158 78.512 73.539 41.490 team72 59.114 50.268 65.876 33.903 25.404 17.194 team73 17.480 87.136 27.001 5.615 57.788 88.698 team74 53.110 42.123 56.285 18.663 75.419 71.128 team75 56.391 35.594 48.240 1.750 90.267 97.382 team76 99.214 55.162 3.345 81.593 87.442 66.650 team77 46.953 83.749 1.146 7.489 4.977 80.452 team78 45.724 4.450 47.499 9.823 29.869 82.283 team79 39.594 75.002 88.492 22.723 82.525 97.911 team80 81.169 42.279 75.647 89.440 11.416 39.335 team81 64.250 39.299 49.818 57.864 96.402 95.548 team82 94.841 24.040 11.958 5.318 59.969 10.779 team83 92.933 1.026 81.710 97.464 78.841 57.344 team84 36.450 8.395 69.400 86.812 36.597 16.455 team85 71.750 24.884 30.636 74.946 79.263 77.997 team86 99.362 91.168 46.240 26.168 59.711 1.738 team87 83.334 34.916 88.320 85.146 25.043 20.107 team88 2.643 31.249 24.757 67.152 83.604 31.640 team89 99.156 45.081 44.858 27.230 88.129 83.337 team90 65.141 24.610 58.167 71.459 18.801 86.023 team91 51.628 76.886 66.395 1.916 90.864 45.338 team92 40.155 87.428 62.177 41.007 27.307 1.300 team93 58.294 20.857 40.273 28.308 1.953 12.584 team94 2.418 39.419 67.587 10.242 37.156 57.060 team95 67.278 49.566 38.350 77.755 89.927 0.652 team96 4.016 89.297 30.993 62.085 17.336 18.329 team97 21.721 61.058 46.024 20.753 50.344 33.152 team98 29.133 14.527 85.909 2.355 84.514 27.198 team99 26.202 79.054 63.522 11.883 52.116 17.222 team100 81.173 48.660 46.727 24.455 84.132 38.186
As I have 10 type-A workers and 10 type-B workers, we end up with 100 possible teams. As we can still use individual workers, our set \(i\) has \(10+10+10\times 10= 120\) elements. As you can see the model will quickly become rather large due to the enumeration of all possible teams.
My first thought was to add a side constraint to the assignment problem:
| Assignment with side-constraint |
|---|
| \[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j} \le 1 &&\forall i\\ & \sum_i \color{darkred}x_{i,j} = 1 &&\forall j \\ & \sum_j \left[\color{darkred}x_{w,j} + \sum_{t|\color{darkblue}{\mathit{team}}(t,w)} \color{darkred}x_{t,j} \right] \le 1 && \forall w \\ & \color{darkred}x_{i,j}\in \{0,1\}\end{align}\] |
If we look at the model more carefully, we see that the last constraint implies the first constraint: any worker or any team can be used only once. That means we can drop the first constraint, and we end up with:
| Final model |
|---|
| \[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\color{darkred}x_{i,j} \\ & \sum_j \left[\color{darkred}x_{w,j} + \sum_{t|\color{darkblue}{\mathit{team}}(t,w)} \color{darkred}x_{t,j} \right] \le 1 && \forall w \\ & \sum_i \color{darkred}x_{i,j} = 1 &&\forall j \\ & \color{darkred}x_{i,j}\in \{0,1\}\end{align}\] |
Results
To obtain a reference point, I first solved the pure assignment problem using only individuals (no teams). This gave:
---- 103 VARIABLE x.L assignment job1 job2 job3 job4 job5 job6 job7 job8 job9 a5 1 a6 1 b1 1 b3 1 b4 1 b6 1 b8 1 b9 1 b10 1 + job10 job11 job12 job13 job14 job15 a1 1 a4 1 a7 1 b2 1 b5 1 b7 1 ---- 103 VARIABLE z.L = 59.379 total cost
When we add teams to the model, we see:
---- 142 VARIABLE x.L assignment job1 job2 job3 job4 job5 job6 job7 job8 job9 a1 1 a5 1 a6 1 b3 1 b4 1 b9 1 b10 1 team17 1 team28 1 + job10 job11 job12 job13 job14 job15 a4 1 a7 1 b2 1 b5 1 team86 1 team91 1 ---- 142 VARIABLE z.L = 40.057 total cost
The objective goes down. That makes sense: we can select some really cheap teams. To verify that we do not select a worker twice, I also generated a different solution report:
---- 153 SET sol alternative solution report
job1 job2 job3 job4 job5 job6 job7 job8 job9
team17.a2 YES
team17.b7 YES
team28.a3 YES
team28.b8 YES
- .a1 YES
- .a5 YES
- .a6 YES
- .b3 YES
- .b4 YES
- .b9 YES
- .b10 YES
+ job10 job11 job12 job13 job14 job15
team86.a9 YES
team86.b6 YES
team91.a10 YES
team91.b1 YES
- .a4 YES
- .a7 YES
- .b2 YES
- .b5 YES
This confirms that workers are not duplicated in the solution.
Finally, some performance numbers. All these models are easy to solve, even the larger ones.
---- 144 PARAMETER results compare statistics assign sidecon final type RMIP MIP MIP vars 301.000 1801.000 1801.000 discr 300.000 1800.000 1800.000 equs 36.000 156.000 36.000 status Optimal Optimal Optimal obj 59.379 40.057 40.057 time 0.172 0.422 0.515 nodes NA iterations 12.000 85.000 85.000
For the MIP models, we see that the solver did not need to use any branching (zero nodes).
Conclusion
I am not sure this model can be used as-is for the purpose described in [1]. It is a good tool to think a bit about the problem, however. Furthermore, it is a good way to assess the quality of solutions when developing heuristics. MIP solvers have the special property that they can provide proven optimal solutions or a gap that gives some indication about the quality of the solution.
References
- Assignment problem with 2 workers per job, https://stackoverflow.com/questions/68482524/assignment-problem-with-2-workers-per-job
Appendix: GAMS model
|
$ontext |
No comments:
Post a Comment