Talent scheduling
कंप्यूटर विज्ञान और संचालन अनुसंधान में प्रतिभा अनुसूचना एक अनुकूलन समस्या है, और यह संयोजन अनुकूलन में भी एक समस्या है। मान लीजिए कि हमें फिल्में बनाने की आवश्यकता है, और प्रत्येक फिल्म में कई दृश्य हैं। प्रत्येक दृश्य को एक या अधिक अभिनेताओं द्वारा शूट किया जाना चाहिए। और मान लीजिए कि आप दिन में केवल एक दृश्य शूट कर सकते हैं। इन अभिनेताओं के वेतन की गणना दिन के हिसाब से की जाती है। इस समस्या में, हम केवल प्रत्येक अभिनेता को लगातार काम पर रख सकते हैं। उदाहरण के लिए, हम पहले और तीसरे दिन एक अभिनेता को नियुक्त नहीं कर सकते हैं, लेकिन दूसरे दिन नहीं। काम पर रखने की अवधि के दौरान, निर्माताओं को अभी भी अभिनेताओं को भुगतान करने की आवश्यकता होती है, भले ही वे फिल्मांकन कार्य में शामिल न हों। टैलेंट शेड्यूलिंग का उद्देश्य दृश्यों के अनुक्रम को समायोजित करके अभिनेताओं के कुल वेतन को कम करना है। गणितीय सूत्रीकरण शूटिंग के दिनों से बनी और कुल अभिनेताओं को शामिल करने वाली फिल्म की शूटिंग पर विचार करें। फिर हम विभिन्न शूटिंग दिनों की आवश्यकताओं का प्रतिनिधित्व करने के लिए डे आउट ऑफ डे मैट्रिक्स (डीओडीएम) का उपयोग करते हैं। द्वारा दी गई प्रविष्टि के साथ मैट्रिक्सः फिर हम वेतन वेक्टर को परिभाषित करते हैं, जिसमें दिया गया th तत्व है जिसका अर्थ है th अभिनेता की प्रति दिन वेतन की दर। मान लीजिए कि v, n स्तंभों के किसी भी क्रमपरिवर्तन को दर्शाता है, हमारे पास हैः n शूटिंग दिनों का क्रमपरिवर्तन सेट है। फिर मैट्रिक्स को इसके कॉलम के क्रमबद्ध होने के अनुसार परिभाषित करें, हमारे पास हैः तब हम एक द्वारा निर्धारित अनुसूची में क्रमशः शुरुआती और नवीनतम दिनों का उपयोग और प्रतिनिधित्व करते हैं जिसके लिए अभिनेता की आवश्यकता होती है। इसलिए हम पा सकते हैं कि अभिनेता को कई दिनों के लिए काम पर रखा जाएगा। लेकिन इन दिनों में, वास्तव में केवल दिनों की आवश्यकता होती है, जिसका अर्थ है कि दिन अनावश्यक हैं, हमारे पास हैः अनावश्यक दिनों की कुल लागत हैः वस्तुनिष्ठ कार्य होगा जिसे हमें कम करना चाहिए। मजबूत एन. पी.-कठोरता का प्रमाण प्रतिभा निर्धारण समस्या में, हम इष्टतम रैखिक व्यवस्था (ओ. एल. ए.) समस्या से कमी करके यह साबित कर सकते हैं कि एन. पी.-कठोर है। और इस समस्या में, यहां तक कि हम प्रत्येक अभिनेता को केवल दो दिनों के लिए प्रतिबंधित करते हैं और सभी अभिनेताओं का वेतन 1 है, यह अभी भी ओ. एल. ए. समस्या के लिए बहुपद रूप से कम है। इस प्रकार, इस समस्या में छद्म-बहुपद एल्गोरिथ्म होने की संभावना नहीं है। पूर्णांक प्रोग्रामिंग पूर्णांक प्रोग्रामिंग मॉडल इस प्रकार दिया गया हैः इस मॉडल में, प्रतिभा के लिए सबसे पहला शूटिंग दिन, प्रतिभा के लिए नवीनतम शूटिंग दिन है, परियोजना के लिए समय निर्धारण है, यानी। संदर्भ इष्टतम समय-निर्धारण