优化黑胶唱片音轨排布：最小化最大面时长的算法实现

我们拥有若干音频音轨与若干称为“面”的分组（对应黑胶唱片的一面），已知每条音轨的名称与时长（秒）。每一面的时长为其上音轨时长之和，所有面中存在一个最大时长，该值随音轨排布方式变化。需找到使最大面时长最小的音轨排布方案，此问题可归约为*Multiway number partitioning（多向数划分）*问题。

用户@erwin-kalvelagen提出使用MIP求解器（CPLEX）求解，但他的GAMS代码存在两处不足：随机生成音轨时长，无法输入指定时长；仅输出各面时长，未给出音轨-面的分配关系。以下是修正后的GAMS代码，解决了上述问题：

set
   i 'songs' /song1*song23/
   j 'sides' /side1*side8/
;

parameter len(i) 'length of song in seconds' / 
song1 323,
song2 289,
song3 329,
song4 424,
song5 351,
song6 369,
song7 298,
song8 296,
song9 358,
song10 358,
song11 342,
song12 275,
song13 300,
song14 280,
song15 283,
song16 348,
song17 347,
song18 357,
song19 243,
song20 244,
song21 255,
song22 308,
song23 360
/;

binary variable x(i,j) 'assignment';
variable z 'maximum length of side';

equations
   maximum(j) 'bound on z'
   assign(i)  'assignment constraints'
   ;
   
maximum(j).. z =g= sum(i, len(i)*x(i,j));
assign(i).. sum(j, x(i,j)) =e= 1;

model m /all/;
option threads=0, mip=cplex;
solve m minimizing z using mip;

parameter slen(j) 'solution: length of sides';
slen(j) = sum(i, len(i)*x.l(i,j));

option decimals = 0;
option x:0:0:1;
display len,slen,z.l,x.l;

NEOS平台CPLEX输出结果（节选） #

Proven optimal solution
MIP Solution:          936.000000    (160060 iterations, 15252 nodes)
Final Solve:           936.000000    (0 iterations)

Best possible:         936.000000
Absolute gap:           -0.000000
Relative gap:           -0.000000

[snip]

----     56 PARAMETER slen  solution: length of sides

side1 936,    side2 936,    side3 936,    side4 793,    side5 931,    side6 936
side7 933,    side8 936


----     56 VARIABLE z.L                   =          936  maximum length of side

----     56 VARIABLE x.L  assignment

song1 .side1 1
song2 .side3 1
song3 .side7 1
song4 .side4 1
song5 .side8 1
song6 .side4 1
song7 .side2 1
song8 .side6 1
song9 .side2 1
song10.side1 1
song11.side8 1
song12.side5 1
song13.side3 1
song14.side2 1
song15.side6 1
song16.side5 1
song17.side3 1
song18.side6 1
song19.side8 1
song20.side7 1
song21.side1 1
song22.side5 1
song23.side7 1

内容的提问来源于stack exchange，提问作者Chris Korda