जॉब-शॉप शेड्यूलिंग

जॉब-शॉप शेड्यूलिंग, जॉब-शॉप प्रॉब्लम (जेएसपी) या जॉब-शॉप शेड्यूलिंग प्रॉब्लम (जेएसएसपी) कंप्यूटर विज्ञान और गतिविधि अनुसंधान में एक अनुकूलन समस्या है। यह इष्टतम कार्य निर्धारण का एक रूप है। एक सामान्य जॉब शेड्यूलिंग प्रॉब्लम में हमें 'n' जॉब्स 'J₁, J₂, ..., J_n दिया जाता है। जिन्हें अलग-अलग प्रसंस्करण समय, जिन्हें अलग-अलग प्रसंस्करण शक्ति वाली M मशीनों पर निर्धारित करने की आवश्यकता होती है, जबकि मेस्पैन को कम करने की प्रयाश करते हुए - शेड्यूल की कुल लंबाई (अर्थात , जब सभी नौकरियों ने प्रसंस्करण समाप्त कर लिया हो)। जॉब-शॉप शेड्यूलिंग के रूप में जाने जाने वाले विशिष्ट संस्करण में, प्रत्येक कार्य में संचालन O₁, O₂, ..., O_n का एक समूह होता है जिन्हें एक विशिष्ट क्रम में संसाधित करने की आवश्यकता होती है (प्राथमिकता बाधाओं के रूप में जाना जाता है)। प्रत्येक ऑपरेशन में एक विशिष्ट मशीन होती है जिस पर उसे संसाधित करने की आवश्यकता होती है और किसी कार्य में केवल एक ही ऑपरेशन को एक निश्चित समय पर संसाधित किया जा सकता है। एक सामान्य छूट 'लचीला' जॉब शॉप है, जहां प्रत्येक ऑपरेशन को किसी दिए गए समूह की किसी भी मशीन पर संसाधित किया जा सकता है (प्रत्येक समूह में मशीनें समान हैं)।

नाम मूल रूप से जॉब शॉप में जॉब शेड्यूलिंग से आया है, किंतु थीम में उस प्रकार के उदाहरणों से परे व्यापक अनुप्रयोग हैं। यह समस्या सबसे प्रसिद्ध मिश्रित अनुकूलन समस्याओं में से एक है, और पहली समस्या थी जिसके लिए 1966 में ग्राहम द्वारा प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) प्रस्तुत किया गया था। मेकस्पैन उद्देश्य के साथ मूलभूत मॉडल के लिए सर्वश्रेष्ठ समस्या उदाहरण टेलार्ड के कारण हैं।

इष्टतम जॉब शेड्यूलिंग समस्याओं के लिए मानक इष्टतम जॉब शेड्यूलिंग तीन-क्षेत्र संकेतन में, जॉब-शॉप वेरिएंट को पहले क्षेत्र में J द्वारा दर्शाया गया है। उदाहरण के लिए, J3$p_{ij}$|$C_{\max }$ द्वारा निरूपित समस्या यूनिट प्रोसेसिंग समय के साथ 3-मशीन जॉब-शॉप समस्या है, जहां लक्ष्य अधिकतम पूर्णता समय को कम करना है।

समस्या भिन्नता

समस्या के कई रूप उपस्थित हैं, जिनमें निम्न सम्मिलित हैं:

• मशीनों में डुप्लिकेट (डुप्लिकेट मशीनों के साथ लचीली जॉब शॉप) हो सकती है या समान मशीनों के समूह (फ्लेक्सिबल जॉब शॉप) से संबंधित हो सकती है।
• मशीनों को नौकरियों या निष्क्रिय समय के बीच एक निश्चित अंतराल की आवश्यकता हो सकती है।
• मशीनों में अनुक्रम-निर्भर समूह अप हो सकते हैं।
• ऑब्जेक्टिव कार्य मेकस्पैन को कम करने के लिए हो सकता है, एलपी स्पेस | L_p मानदंड, विलंबता, अधिकतम विलंबता आदि। यह बहुउद्देश्यीय अनुकूलन समस्या भी हो सकती है।
• जॉब में बाधाएँ हो सकती हैं, उदाहरण के लिए जॉब j को प्रारंभ करने से पहले मुझे एक जॉब को पूरा करना होगा ( कार्यप्रवाह देखें) साथ ही, उद्देश्य कार्य बहु-मापदंड हो सकता है।
• कार्यों का समूह मशीनों के विभिन्न समूह से संबंधित हो सकता है।
• नियतात्मक (निश्चित) प्रसंस्करण समय या संभाव्य प्रसंस्करण समय।

एनपी-कठोरता

चूंकि ट्रैवलिंग सेल्समैन की समस्या एनपी कठिन है, अनुक्रम-निर्भर समूह अप के साथ जॉब-शॉप की समस्या भी स्पष्ट रूप से एनपी-हार्ड है क्योंकि टीएसपी एक ही काम के साथ जेएसपी का एक विशेष स्थिति है (शहर मशीन हैं और सेल्समैन नौकरी है)।

समस्या प्रतिनिधित्व

वियोगी ग्राफ जॉब-शॉप शेड्यूलिंग समस्या उदाहरणों का वर्णन करने के लिए उपयोग किए जाने वाले लोकप्रिय मॉडलों में से एक है।

समस्या का गणितीय कथन निम्नानुसार बनाया जा सकता है:

माना $M=\{M_{1},M_{2},\dots ,M_{m}\}$ और $J=\{J_{1},J_{2},\dots ,J_{n}\}$ दो हैं परिमित समूह समस्या की औद्योगिक उत्पत्ति के कारण, $\displaystyle M_{i}$ को मशीन कहा जाता है और $\displaystyle J_{j}$ को जॉब कहा जाता है।

होने देना $\displaystyle \ {\mathcal {X}}$ मशीनों को नौकरियों के सभी अनुक्रमिक असाइनमेंट के समूह को निरूपित करें, जैसे कि प्रत्येक मशीन द्वारा प्रत्येक कार्य को ठीक एक बार किया जाता है; तत्वों $x\in {\mathcal {X}}$ रूप में लिखा जा सकता है $n\times m$ मैट्रिसेस, किस स्तम्भ में $\displaystyle i$ उस मशीन की नौकरियों को सूचीबद्ध करता है जो मशीन $\displaystyle M_{i}$ क्रम से करेगी। उदाहरण के लिए, मैट्रिक्स

$x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}$

इसका अर्थ है वह मशीन $\displaystyle M_{1}$ तीन काम $\displaystyle J_{1},J_{2},J_{3}$ $\displaystyle J_{1},J_{2},J_{3}$ के क्रम में करेगी।जबकि मशीन $\displaystyle M_{2}$ कार्यों को $\displaystyle J_{2},J_{3},J_{1}$के क्रम में करेगी।

यह भी मान लीजिए कि कुछ लागत फलन $C:{\mathcal {X}}\to [0,+\infty ]$ है लागत कार्य की व्याख्या कुल प्रसंस्करण समय के रूप में की जा सकती है, और समय के संदर्भ में कुछ अभिव्यक्ति हो सकती है $C_{ij}:M\times J\to [0,+\infty ]$, मशीन के लिए लागत/समय $\displaystyle M_{i}$ नौकरी करना $\displaystyle J_{j}$ है

जॉब-शॉप समस्या जॉब $x\in {\mathcal {X}}$ का एक असाइनमेंट खोजने के लिए है, जैसे कि $\displaystyle C(x)$ एक न्यूनतम है, अर्थात, कोई $y\in {\mathcal {X}}$ ऐसा नहीं $\displaystyle C(x)>C(y)$ है

निर्धारण दक्षता

शेड्यूलिंग दक्षता को कुल मशीन निष्क्रिय समय के कुल प्रसंस्करण समय के अनुपात के माध्यम से शेड्यूल के लिए परिभाषित किया जा सकता है:

$C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}$

यहाँ $l_{i}$ मशीन का निष्क्रिय समय है $i$, $C$ मेकअप है और $m$ मशीनों की संख्या है। ध्यान दें कि उपरोक्त परिभाषा के साथ, शेड्यूलिंग दक्षता केवल मशीनों की संख्या और कुल प्रसंस्करण समय के लिए सामान्यीकृत मेकस्पैन है। यह विभिन्न आकार के जेएसपी उदाहरणों में संसाधनों के उपयोग की तुलना करना संभव बनाता है।

अनंत लागत की समस्या

जेएसपी में जिन पहली समस्याओं से निपटा जाना चाहिए उनमें से एक यह है कि कई प्रस्तावित समाधानों की लागत अनंत है: अर्थात $x_{\infty }\in {\mathcal {X}}$ उपस्थित है ऐसा है कि $C(x_{\infty })=+\infty$. वास्तव में, ऐसे $x_{\infty }$ उदाहरणों की कल्पना करना बहुत सरल है यह सुनिश्चित करके कि दो मशीनें गतिरोध करेंगी, जिससे प्रत्येक दूसरे के अगले चरण के आउटपुट की प्रतीक्षा करे।

प्रमुख परिणाम

ग्राहम ने पहले ही 1966 में लिस्ट शेड्यूलिंग एल्गोरिथम प्रदान कर दिया था, जो है (2 − 1/m)-प्रतिस्पर्धी, जहां m मशीनों की संख्या है। साथ ही, यह भी सिद्ध हुआ कि सूची निर्धारण 2 और 3 मशीनों के लिए इष्टतम ऑनलाइन एल्गोरिथम है। कॉफ़मैन-ग्राहम एल्गोरिथम (1972) समान-लंबाई वाली नौकरियों के लिए भी दो मशीनों के लिए इष्टतम है, और है (2 − 2/m)-प्रतिस्पर्द्धी 1992 में, बार्टल, फिएट, कार्लॉफ़ और वोहरा ने एक एल्गोरिथ्म प्रस्तुत किया जो 1.986 प्रतिस्पर्धी है। 1994 में कार्गर, फिलिप्स और टॉरंग द्वारा एक 1.945-प्रतिस्पर्धी एल्गोरिदम प्रस्तुत किया गया था। 1992 में, एल्बर्स ने एक अलग एल्गोरिथ्म प्रदान किया जो 1.923-प्रतिस्पर्धी है। वर्तमान में, सबसे अच्छा ज्ञात परिणाम फ्लीशर और वाहल द्वारा दिया गया एक एल्गोरिदम है, जो 1.9201 के प्रतिस्पर्धी अनुपात को प्राप्त करता है।

एल्बर्स द्वारा 1.852 की निचली सीमा प्रस्तुत की गई थी। मेकस्पैन उद्देश्य के साथ जॉब-शॉप शेड्यूलिंग विकसित करने में टेलार्ड इंस्टेंसेस की महत्वपूर्ण भूमिका है।

1976 में गैरी ने एक प्रमाण प्रदान किया कि यह समस्या m>2 के लिए NP-पूर्ण है, अर्थात, तीन या अधिक मशीनों के लिए नियतात्मक बहुपद समय में किसी भी इष्टतम समाधान की गणना नहीं की जा सकती है (जब तक कि P=NP न हो)।

2011 में शिन चेन एट अल। पिछले परिणामों में सुधार करते हुए दो संबंधित मशीनों पर ऑनलाइन शेड्यूलिंग के लिए इष्टतम एल्गोरिदम प्रदान किया।

ऑफ़लाइन मेकस्पैन न्यूनीकरण

परमाणु नौकरियां

See also: मल्टीप्रोसेसर शेड्यूलिंग

ऑफ़लाइन मेकस्पैन मिनिमाइज़ेशन समस्या का सबसे सरल रूप परमाणु नौकरियों से संबंधित है, अर्थात ऐसी नौकरियां जो कई ऑपरेशनों में उप-विभाजित नहीं हैं। यह विभिन्न विभिन्न आकारों की कई वस्तुओं को एक निश्चित संख्या में डिब्बे में पैक करने के समान है, जैसे कि आवश्यक अधिकतम बिन आकार जितना संभव हो उतना छोटा हो (यदि इसके अतिरिक्त डिब्बे की संख्या को कम करना है, और बिन का आकार तय किया गया है, तो समस्या एक अलग समस्या बन जाती है, जिसे बिन पैकिंग समस्या के रूप में जाना जाता है।)

डोरित एस. होचबौम और डेविड शमोयस ने 1987 में एक बहुपद-समय सन्निकटन योजना प्रस्तुत की जो स्पष्टता की किसी भी वांछित डिग्री के लिए परमाणु नौकरियों के साथ ऑफ़लाइन मेकस्पैन न्यूनीकरण समस्या का अनुमानित समाधान खोजती है।

कई कार्यों से युक्त नौकरियां

M मशीनों पर कई (M) संचालन के साथ शेड्यूलिंग नौकरियों की समस्या का मूल रूप, जैसे कि पहले के सभी ऑपरेशन पहली मशीन पर किए जाने चाहिए, दूसरे के सभी ऑपरेशन दूसरे पर आदि, और एक काम समानांतर में नहीं किया जा सकता है, इसे फ्लो-शॉप शेड्यूलिंग समस्या के रूप में जाना जाता है। जेनेटिक एल्गोरिद्म सहित विभिन्न एल्गोरिदम उपस्थित हैं।

जॉनसन का एल्गोरिथम

See also: जॉनसन का नियम

एसएम जॉनसन द्वारा एक हेयुरिस्टिक एल्गोरिदम का उपयोग 2 मशीन एन जॉब समस्या के स्थिति को हल करने के लिए किया जा सकता है जब सभी नौकरियों को एक ही क्रम में संसाधित किया जाना हो। एल्गोरिथ्म के चरण इस प्रकार हैं:

जॉब P_i के दो ऑपरेशन हैं, अवधि P_i1, P_i2, मशीन M1, M2 पर उस क्रम में किए जाने हैं।

• चरण 1. सूची A = {1, 2, …, N}, सूची L1 = {}, सूची L2 = {}।
• चरण 2. सभी उपलब्ध संचालन अवधियों में से न्यूनतम चुनें।

यदि न्यूनतम P_k1 से संबंधित है,

सूची A से K को हटा दें; सूची L1 के अंत में K जोड़ें।

यदि न्यूनतम P_k2 से संबंधित है,

सूची A से K को हटा दें; सूची L2 की प्रारंभ में K जोड़ें।

• चरण 3. सूची A के खाली होने तक चरण 2 को दोहराएं।
• चरण 4. सूची L1, सूची L2 में सम्मिलित हों। यह इष्टतम क्रम है।

जॉनसन की विधि केवल दो मशीनों के लिए उत्तम काम करती है। , चूंकि यह इष्टतम और गणना करने में आसान है, कुछ शोधकर्ताओं ने इसे M मशीनों के (M > 2.) लिए अपनाने की प्रयाश की है,

यह विचार इस प्रकार है: कल्पना कीजिए कि प्रत्येक कार्य के लिए M1, M2… Mm पर अनुक्रम में m संचालन की आवश्यकता होती है। हम पहली m/2 मशीनों को एक (काल्पनिक) मशीनिंग केंद्र, MC1, और शेष मशीनों को एक मशीनिंग केंद्र MC2 में संयोजित करते हैं। फिर MC1 पर जॉब P के लिए कुल प्रोसेसिंग समय = योग (पहली m/2 मशीनों पर संचालन समय), और MC2 पर जॉब P के लिए प्रोसेसिंग समय = योग (अंतिम m/2 मशीनों पर संचालन समय)।

ऐसा करके हमने M-मशीन की समस्या को टू मशीनिंग सेंटर शेड्यूलिंग समस्या में बदल दिया है। हम इसे जॉनसन की विधि से हल कर सकते हैं।

मेकस्पैन पूर्वानुमान

मशीन लर्निंग का उपयोग हाल ही में इष्टतम शेड्यूल तैयार किए बिना जेएसपी उदाहरण के इष्टतम मेकस्पैन की पूर्वानुमान करने के लिए किया गया है। प्रारंभिक परिणाम लगभग 80% की स्पष्टता दिखाते हैं जब पर्यवेक्षित मशीन सीखने के विधियों को औसत की तुलना में उनकी इष्टतम शेड्यूलिंग दक्षता के आधार पर छोटे यादृच्छिक रूप से उत्पन्न जेएसपी उदाहरणों को वर्गीकृत करने के लिए प्रयुक्त किया गया था।

उदाहरण

संकेतक बाधाओं के साथ मिश्रित-पूर्णांक प्रोग्रामिंग समस्या के रूप में एएमपीएल में तैयार की गई जॉब-शॉप शेड्यूलिंग समस्या का एक उदाहरण यहां दिया गया है:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param ProcessingTime:
1 2 3 4 :=
1 4 2 1
2 3 6 2
3 7 2 3
4 1 5 8;

संबंधित समस्याएं

• फ्लो-शॉप शेड्यूलिंग एक समान समस्या है किंतु बिना किसी बाधा के कि प्रत्येक ऑपरेशन एक विशिष्ट मशीन पर किया जाना चाहिए (केवल क्रम की कमी रखी जाती है)।
• ओपन-शॉप शेड्यूलिंग एक ऐसी ही समस्या है, किंतु क्रम की कमी के बिना भी है ।

यह भी देखें

• वियोगी ग्राफ
• गतिशील प्रोग्रामिंग
• जेनेटिक एल्गोरिदम शेड्यूलिंग
• एनपी-पूर्ण समस्याओं की सूची
• इष्टतम नियंत्रण
• निर्धारण (उत्पादन प्रक्रियाएं)

बाहरी संबंध

• University of Vienna Directory of methodologies, systems and software for dynamic optimization.
• Taillard instances
• Brucker P. Scheduling Algorithms. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0