Talent scheduling
திறமை திட்டமிடல் என்பது கணினி அறிவியல் மற்றும் செயல்பாட்டு ஆராய்ச்சியில் ஒரு உகப்பாக்கம் சிக்கலாகும், மேலும் இது ஒருங்கிணைந்த உகப்பாக்கத்தில் ஒரு சிக்கலாகும். நாம் திரைப்படங்களை உருவாக்க வேண்டும் என்று வைத்துக்கொள்வோம், ஒவ்வொரு படத்திலும் பல காட்சிகள் உள்ளன. ஒவ்வொரு காட்சியையும் ஒன்று அல்லது அதற்கு மேற்பட்ட நடிகர்கள் படமாக்க வேண்டும். நீங்கள் ஒரு நாளைக்கு ஒரு காட்சியை மட்டுமே படமாக்க முடியும் என்று வைத்துக்கொள்வோம். இந்த நடிகர்களின் சம்பளம் நாளுக்கு நாள் கணக்கிடப்படுகிறது. இந்த சிக்கலில், ஒவ்வொரு நடிகரையும் தொடர்ச்சியாக மட்டுமே பணியமர்த்த முடியும். உதாரணமாக, முதல் மற்றும் மூன்றாவது நாட்களில் ஒரு நடிகரை நாம் பணியமர்த்த முடியாது, ஆனால் இரண்டாவது நாளில் அல்ல. பணியமர்த்தல் காலத்தில், தயாரிப்பாளர்கள் படப்பிடிப்பு பணியில் ஈடுபடாவிட்டாலும் நடிகர்களுக்கு பணம் செலுத்த வேண்டும். காட்சிகளின் வரிசையை சரிசெய்வதன் மூலம் நடிகர்களின் மொத்த சம்பளத்தைக் குறைப்பதே திறமை திட்டமிடலின் நோக்கமாகும். கணித சூத்திரம் படப்பிடிப்பு நாட்களைக் கொண்ட மற்றும் மொத்தம் நடிகர்களை உள்ளடக்கிய ஒரு திரைப்பட படப்பிடிப்பைக் கவனியுங்கள். பின்னர் பல்வேறு படப்பிடிப்பு நாட்களுக்கான தேவைகளைக் குறிக்க டே அவுட் ஆஃப் டேஸ் மேட்ரிக்ஸ் (டிஓடிஎம்) ஐப் பயன்படுத்துகிறோம். கொடுக்கப்பட்ட உள்ளீட்டுடன் மேட்ரிக்ஸ்ஃ பின்னர் நாம் ஊதிய திசையனை வரையறுக்கிறோம், இதன் மூலம் கொடுக்கப்பட்ட th உறுப்பு என்பது th நடிகரின் ஒரு நாளைக்கு ஊதிய விகிதம் என்று பொருள்படும். v என்பது n நெடுவரிசைகளின் எந்த வரிசைமாற்றத்தையும் குறிக்கட்டும், நம்மிடம் உள்ளதுஃ இது n படப்பிடிப்பு நாட்களின் வரிசைமாற்ற தொகுப்பாகும். பின்னர் மேட்ரிக்ஸை அதன் நெடுவரிசைகளுடன் வரிசைப்படுத்தப்பட்டபடி வரையறுக்கவும், நம்மிடம் உள்ளதுஃ பின்னர் நாம் பயன்படுத்துகிறோம் மற்றும் குறிப்பிடுவதற்கு நடிகர்கள் தேவைப்படும் அட்டவணையில் முறையே ஆரம்ப மற்றும் சமீபத்திய நாட்களைக் குறிக்கிறோம். எனவே சில நாட்களுக்கு நடிகர் பணியமர்த்தப்படுவார் என்பதை நாம் காணலாம். ஆனால் இந்த நாட்களில், நாட்கள் மட்டுமே உண்மையில் தேவைப்படுகின்றன, அதாவது நாட்கள் தேவையற்றவை, நம்மிடம் உள்ளனஃ தேவையற்ற நாட்களின் மொத்த செலவுஃ நாம் குறைக்க வேண்டிய புறநிலை செயல்பாடாக இருக்கும். வலுவான NP-கடினத்தன்மையின் சான்று திறமை திட்டமிடல் சிக்கலில், உகந்த நேரியல் ஏற்பாடு (OLA) சிக்கலில் இருந்து குறைப்பதன் மூலம் NP-கடினமானது என்பதை நாம் நிரூபிக்க முடியும். இந்த சிக்கலில், ஒவ்வொரு நடிகருக்கும் இரண்டு நாட்கள் மட்டுமே தேவைப்படுகிறது மற்றும் அனைத்து நடிகர்களின் சம்பளமும் 1 ஆகும், இது இன்னும் ஓ. எல். ஏ சிக்கலுக்கு பல்லுறுப்புக்கோவை குறைக்கப்படுகிறது. எனவே, இந்த சிக்கல் போலி-பல்லுறுப்புக்கோவை வழிமுறையைக் கொண்டிருக்க வாய்ப்பில்லை. முழு எண் நிரலாக்கம் முழு எண் நிரலாக்க மாதிரி பின்வருமாறு வழங்கப்படுகிறதுஃ இந்த மாதிரியில், திறமைக்கான ஆரம்பகால படப்பிடிப்பு நாள், திறமைக்கான சமீபத்திய படப்பிடிப்பு நாள், திட்டத்திற்கான திட்டமிடல், அதாவது. குறிப்புகள் உகந்த திட்டமிடல்