libretime/legacy/application/models
dakriy 5b5c68c628
feat(legacy): implement subset sum solution to show scheduling (#3019)
### Description

When running a radio station it is generally a good idea to reduce dead
air time. The current algorithm for adding tracks to a block/show can
leave a lot of dead air time at the end as it doesn't use a very good
algorithm. Adding tracks to a show until it is full while making it as
full as possible is a well known problem in computer science. It is the
[Subset Sum Problem](https://en.wikipedia.org/wiki/Subset_sum_problem).
This PR implements a Randomized Greedy with Local Improvement (RGLI)
approximation solution for the Subset Sum Problem. The new algorithm is
only used when sort type is random and overflow is not enabled and there
is no limit on the number of tracks that can be used.

**This is a new feature**:

Improvement on an existing feature. 

**I have not updated the documentation to reflect these changes**:

I did not update the documentation because the current scheduling
algorithm is not currently documented and its existing features have not
changed.

### Testing Notes

**What I did:**

I first attempted a fully polynomial time approximation scheme solution,
however it is really bad at finding good solutions for high density
values and can kinda slow the more tracks/time you have. So I instead
implemented an RGLI which is O(nlogn) and has been giving much better
results.

I implemented the solution in a separate project and tested it and timed
the values with a normal distribution of 500 songs with a mean of 3
minutes and a standard deviation of 1 minute. With a show size of 1 hour
the algorithm took around 10-15 ms to run. When adjusting the block size
and track size the algorithm still was pretty quick to run. Am going to
be testing on an instance with lots of tracks later, will update PR when
I have done that.

**How you can replicate my testing:**

_How can the reviewer validate this PR?_

### **Links**

Closes #3018
2024-10-13 15:31:08 +02:00
..
airtime fix(deps): update dependency friendsofphp/php-cs-fixer to <3.53.1 (#2972) 2024-04-13 14:36:31 +02:00
formatters style(legacy): fix code format with php-cs-fixer (#1674) 2022-03-14 12:15:04 +02:00
tests feat: build schedule events exclusively in playout (#2946) 2024-04-27 20:09:16 +02:00
Auth.php feat(legacy): move session store to database (#2523) 2023-05-30 22:25:50 +02:00
Block.php feat(legacy): implement subset sum solution to show scheduling (#3019) 2024-10-13 15:31:08 +02:00
Criteria.php feat(legacy): add filename block criteria (#3015) 2024-06-22 11:51:59 +02:00
Dashboard.php style(legacy): format files (#1946) 2022-07-07 20:01:15 +02:00
Datatables.php fix(legacy): advanced search by track type id 2023-01-08 22:40:48 +02:00
Email.php Format code using php-cs-fixer 2021-10-12 11:07:56 +02:00
FreeIpa.php Format code using php-cs-fixer 2021-10-12 11:07:56 +02:00
Library.php fix: use constrained foreign key for files track_type 2022-07-07 21:07:41 +02:00
LibraryEditable.php Format code using php-cs-fixer 2021-10-12 11:07:56 +02:00
ListenerStat.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.26.1 (main) (#2677) 2023-09-08 15:45:24 +02:00
LiveLog.php style(legacy): format files (#1946) 2022-07-07 20:01:15 +02:00
Locale.php feat: add Norwegian Bokmål locale (#3073) 2024-09-06 14:43:40 +01:00
LoginAttempts.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.26.1 (main) (#2677) 2023-09-08 15:45:24 +02:00
Playlist.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.27.1 (main) (#2714) 2023-09-17 17:14:59 +02:00
Preference.php fix(legacy): replay_gain_modifier should be a system preference (#2943) 2024-02-08 19:48:49 +01:00
RabbitMq.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.46.1 (main) (#2868) 2024-01-07 13:59:02 +01:00
Schedule.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.27.1 (main) (#2714) 2023-09-17 17:14:59 +02:00
Scheduler.php fix: playlist allocates inaccurate time to smartblocks (#3026) 2024-06-05 17:01:57 +01:00
ServiceRegister.php fix(legacy): update or remove broken links 2022-09-21 08:28:43 +02:00
Show.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.23.1 (stable) (#2656) 2023-08-15 18:28:18 +02:00
ShowBuilder.php style(legacy): format files (#1946) 2022-07-07 20:01:15 +02:00
ShowInstance.php feat(legacy): trim overbooked shows after autoloading a playlist (#2897) 2024-02-02 20:17:23 +01:00
StoredFile.php feat(legacy): show filename and size on edit page and add filename datatable column (#3083) 2024-10-13 08:45:54 +01:00
StreamSetting.php feat: add mobile devices stream config field (#2744) 2023-10-14 08:13:04 +01:00
Subjects.php chore: use https links (#2075) 2022-08-25 16:25:54 +02:00
Systemstatus.php chore(legacy): format code 2022-09-12 14:15:50 +02:00
Tracktype.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.27.1 (main) (#2714) 2023-09-17 17:14:59 +02:00
User.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.43.2 (main) (#2848) 2023-12-29 15:28:57 +01:00
Webstream.php fix(deps): update dependency friendsofphp/php-cs-fixer to <3.27.1 (main) (#2714) 2023-09-17 17:14:59 +02:00