Talent scheduling
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ಮತ್ತು ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಶೋಧನೆಯಲ್ಲಿ ಟ್ಯಾಲೆಂಟ್ ಶೆಡ್ಯೂಲಿಂಗ್ ಒಂದು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿದೆ ಮತ್ತು ಇದು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಷನ್ನಲ್ಲಿಯೂ ಸಹ ಸಮಸ್ಯೆಯಾಗಿದೆ. ನಾವು ಚಲನಚಿತ್ರಗಳನ್ನು ನಿರ್ಮಿಸಬೇಕಾಗಿದೆ ಎಂದು ಭಾವಿಸೋಣ, ಮತ್ತು ಪ್ರತಿ ಚಲನಚಿತ್ರವು ಹಲವಾರು ದೃಶ್ಯಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಪ್ರತಿ ದೃಶ್ಯವನ್ನು ಒಬ್ಬ ಅಥವಾ ಹೆಚ್ಚು ನಟರು ಚಿತ್ರೀಕರಿಸಬೇಕಾಗುತ್ತದೆ. ಮತ್ತು ನೀವು ದಿನಕ್ಕೆ ಒಂದು ದೃಶ್ಯವನ್ನು ಮಾತ್ರ ಚಿತ್ರೀಕರಿಸಬಹುದು ಎಂದು ಭಾವಿಸೋಣ. ಈ ನಟರ ಸಂಬಳವನ್ನು ದಿನದಿಂದ ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು ಪ್ರತಿ ನಟನನ್ನು ಅನುಕ್ರಮವಾಗಿ ಮಾತ್ರ ನೇಮಿಸಿಕೊಳ್ಳಬಹುದು. ಉದಾಹರಣೆಗೆ, ನಾವು ಮೊದಲ ಮತ್ತು ಮೂರನೇ ದಿನಗಳಲ್ಲಿ ನಟರನ್ನು ನೇಮಿಸಿಕೊಳ್ಳಲು ಸಾಧ್ಯವಿಲ್ಲ, ಆದರೆ ಎರಡನೇ ದಿನವಲ್ಲ. ನೇಮಕದ ಅವಧಿಯಲ್ಲಿ, ನಿರ್ಮಾಪಕರು ನಟರು ಚಿತ್ರೀಕರಣದ ನಿಯೋಜನೆಯಲ್ಲಿ ಭಾಗಿಯಾಗಿಲ್ಲದಿದ್ದರೂ ಅವರಿಗೆ ಹಣ ಪಾವತಿಸಬೇಕಾಗುತ್ತದೆ. ದೃಶ್ಯಗಳ ಅನುಕ್ರಮವನ್ನು ಸರಿಹೊಂದಿಸುವ ಮೂಲಕ ನಟರ ಒಟ್ಟು ವೇತನವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಪ್ರತಿಭೆಯ ವೇಳಾಪಟ್ಟಿಯ ಉದ್ದೇಶವಾಗಿದೆ. ಗಣಿತದ ಸೂತ್ರೀಕರಣ ಚಿತ್ರೀಕರಣದ ದಿನಗಳನ್ನು ಒಳಗೊಂಡ ಮತ್ತು ಒಟ್ಟು ನಟರನ್ನು ಒಳಗೊಂಡ ಚಲನಚಿತ್ರ ಚಿತ್ರೀಕರಣವನ್ನು ಪರಿಗಣಿಸಿ. ನಂತರ ನಾವು ವಿವಿಧ ಶೂಟಿಂಗ್ ದಿನಗಳ ಅವಶ್ಯಕತೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಡೇ ಔಟ್ ಆಫ್ ಡೇಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ (ಡಿಒಡಿಎಂ) ಅನ್ನು ಬಳಸುತ್ತೇವೆ. ನೀಡಿದ ನಮೂದಿನೊಂದಿಗೆ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಃ ನಂತರ ನಾವು ವೇತನ ವಾಹಕವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ, ಅದರಲ್ಲಿ ನೀಡಲಾದ ಒಂಬತ್ತನೇ ಅಂಶವು ಒಂಬತ್ತನೇ ನಟನ ದಿನಕ್ಕೆ ವೇತನದ ದರವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ನಾವು ಹೊಂದಿರುವ n ಕಾಲಮ್ಗಳ ಯಾವುದೇ ಕ್ರಮಪಲ್ಲಟನೆಯನ್ನು v ಸೂಚಿಸೋಣಃ ಇದು n ಶೂಟಿಂಗ್ ದಿನಗಳ ಕ್ರಮಪಲ್ಲಟನೆ ಸೆಟ್ ಆಗಿದೆ. ನಂತರ ಅದರ ಕಾಲಮ್ಗಳನ್ನು ಕ್ರಮಬದ್ಧಗೊಳಿಸಿದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿ, ನಾವು ಹೊಂದಿದ್ದೇವೆಃ ನಂತರ ನಾವು ಬಳಸುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿನಿಧಿಸಲು ಅನುಕ್ರಮವಾಗಿ ವೇಳಾಪಟ್ಟಿಯಲ್ಲಿ ಆರಂಭಿಕ ಮತ್ತು ಇತ್ತೀಚಿನ ದಿನಗಳನ್ನು ಸೂಚಿಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ ನಟರನ್ನು ದಿನಗಳವರೆಗೆ ನೇಮಿಸಿಕೊಳ್ಳಲಾಗುತ್ತದೆ ಎಂದು ನಾವು ಕಂಡುಕೊಳ್ಳಬಹುದು. ಆದರೆ ಈ ದಿನಗಳಲ್ಲಿ, ದಿನಗಳು ಮಾತ್ರ ನಿಜವಾಗಿಯೂ ಬೇಕಾಗುತ್ತವೆ, ಅಂದರೆ ದಿನಗಳು ಅನಗತ್ಯವಾಗಿವೆ, ನಮ್ಮ ಬಳಿಃ ಅನಗತ್ಯ ದಿನಗಳ ಒಟ್ಟು ವೆಚ್ಚವೆಂದರೆಃ ನಾವು ಕಡಿಮೆ ಮಾಡಬೇಕಾದ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯವಾಗಿರುತ್ತದೆ. ಬಲವಾದ ಎನ್ಪಿ-ಗಡಸುತನದ ಪುರಾವೆ ಪ್ರತಿಭೆಯ ವೇಳಾಪಟ್ಟಿ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಆಪ್ಟಿಮಲ್ ಲೀನಿಯರ್ ಅರೇಂಜ್ಮೆಂಟ್ (ಒಎಲ್ಎ) ಸಮಸ್ಯೆಯಿಂದ ಕಡಿತಗೊಳಿಸುವ ಮೂಲಕ ನಾವು ಅದನ್ನು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ಸಾಬೀತುಪಡಿಸಬಹುದು. ಮತ್ತು ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು ಪ್ರತಿ ನಟನನ್ನು ಕೇವಲ ಎರಡು ದಿನಗಳವರೆಗೆ ನಿರ್ಬಂಧಿಸುತ್ತೇವೆ ಮತ್ತು ಎಲ್ಲಾ ನಟರ ಸಂಬಳವು 1 ಆಗಿರುತ್ತದೆ, ಇದು ಇನ್ನೂ ಒಎಲ್ಎ ಸಮಸ್ಯೆಗೆ ಬಹುಪದೀಯವಾಗಿ ಕಡಿತಗೊಳ್ಳುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಸಮಸ್ಯೆಯು ಹುಸಿ-ಬಹುಪದೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಹೊಂದುವ ಸಾಧ್ಯತೆಯಿಲ್ಲ. ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಪೂರ್ಣಾಂಕ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮಾದರಿಯನ್ನು ಹೀಗೆ ನೀಡಲಾಗಿದೆಃ ಈ ಮಾದರಿಯಲ್ಲಿ, ಅಂದರೆ ಪ್ರತಿಭೆಗಾಗಿ ಆರಂಭಿಕ ಶೂಟಿಂಗ್ ದಿನ, ಪ್ರತಿಭೆಗಾಗಿ ಇತ್ತೀಚಿನ ಶೂಟಿಂಗ್ ದಿನ, ಯೋಜನೆಯ ವೇಳಾಪಟ್ಟಿ, ಅಂದರೆ. ಉಲ್ಲೇಖಗಳ ಅತ್ಯುತ್ತಮ ವೇಳಾಪಟ್ಟಿ