Talent scheduling
প্রতিভা সময়সূচী কম্পিউটার বিজ্ঞান এবং অপারেশন গবেষণায় একটি অপ্টিমাইজেশান সমস্যা, এবং এটি সমন্বিত অপ্টিমাইজেশনের ক্ষেত্রেও একটি সমস্যা। ধরুন আমাদের চলচ্চিত্র তৈরি করতে হবে, এবং প্রতিটি ছবিতে বেশ কয়েকটি দৃশ্য রয়েছে। প্রতিটি দৃশ্যের শ্যুটিং করতে হবে এক বা একাধিক অভিনেতাকে। এবং ধরুন আপনি দিনে মাত্র একটি দৃশ্যের শ্যুটিং করতে পারেন। এই অভিনেতাদের বেতন দিনের ভিত্তিতে গণনা করা হয়। এই সমস্যায়, আমরা কেবল প্রতিটি অভিনেতাকে পরপর নিয়োগ করতে পারি। উদাহরণস্বরূপ, আমরা প্রথম এবং তৃতীয় দিনে কোনও অভিনেতাকে নিয়োগ করতে পারি না, তবে দ্বিতীয় দিনে নয়। নিয়োগের সময়কালে, নির্মাতাদের চিত্রগ্রহণের কাজে জড়িত না থাকলেও অভিনেতাদের অর্থ প্রদান করতে হয়। প্রতিভা নির্ধারণের উদ্দেশ্য হল দৃশ্যের ক্রম সামঞ্জস্য করে অভিনেতাদের মোট বেতন হ্রাস করা। গাণিতিক সূত্র শ্যুটিংয়ের দিনগুলি নিয়ে গঠিত এবং মোট অভিনেতাদের জড়িত একটি চলচ্চিত্রের শ্যুটিং বিবেচনা করুন। তারপর আমরা বিভিন্ন শুটিং দিনের প্রয়োজনীয়তা উপস্থাপন করতে ডে আউট অফ ডে ম্যাট্রিক্স (ডিওডিএম) ব্যবহার করি। প্রদত্ত এন্ট্রি সহ ম্যাট্রিক্সঃ তারপরে আমরা বেতন ভেক্টরকে সংজ্ঞায়িত করি, যার দ্বারা প্রদত্ত তম উপাদানটির অর্থ হল তম অভিনেতার প্রতিদিন বেতনের হার। ধরা যাক v হল n কলামগুলির যে কোনও বিন্যাসকে বোঝায়, আমাদের আছেঃ হল n শুটিং দিনের বিন্যাস সেট। তারপর ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করুন যার কলামগুলি ক্রমবর্ধমান অনুসারে, আমাদের আছেঃ তারপর আমরা ব্যবহার করি এবং প্রতিনিধিত্ব করি যথাক্রমে একটি দ্বারা নির্ধারিত সময়সূচির প্রথম এবং সর্বশেষ দিনগুলিকে বোঝাতে যার জন্য অভিনেতার প্রয়োজন হয়। তাই আমরা দেখতে পাচ্ছি যে অভিনেতাদের কয়েক দিনের জন্য ভাড়া করা হবে। কিন্তু এই দিনগুলিতে, শুধুমাত্র দিনের প্রয়োজন হয়, যার অর্থ হল দিনগুলি অপ্রয়োজনীয়, আমাদের আছেঃ অপ্রয়োজনীয় দিনের মোট খরচ হবেঃ বস্তুনিষ্ঠ ফাংশন যা আমাদের হ্রাস করা উচিত। শক্তিশালী এনপি-কঠোরতার প্রমাণ প্রতিভা নির্ধারণের সমস্যায়, আমরা সর্বোত্তম রৈখিক বিন্যাস (ওএলএ) সমস্যা থেকে হ্রাস করে প্রমাণ করতে পারি যে এটি এনপি-শক্ত। এবং এই সমস্যায়, এমনকি আমরা প্রতিটি অভিনেতাকে মাত্র দুই দিনের জন্য সীমাবদ্ধ করি এবং সমস্ত অভিনেতাদের বেতন 1 হয়, এটি এখনও ও. এল. এ সমস্যার জন্য বহুপদীভাবে হ্রাসযোগ্য। সুতরাং, এই সমস্যার ছদ্ম-বহুপদী অ্যালগরিদম থাকার সম্ভাবনা কম। পূর্ণসংখ্যা প্রোগ্রামিং পূর্ণসংখ্যা প্রোগ্রামিং মডেলটি দ্বারা দেওয়া হয়ঃ এই মডেলে, মানে প্রতিভার জন্য প্রথম শুটিং দিন, প্রতিভার জন্য সর্বশেষ শুটিং দিন, প্রকল্পের সময়সূচী, অর্থাৎ। রেফারেন্স সর্বোত্তম সময়সূচী