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

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

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

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

समस्या के कई रूप मौजूद हैं, जिनमें निम्न शामिल हैं:

• मशीनों में डुप्लिकेट (डुप्लिकेट मशीनों के साथ लचीली जॉब शॉप) हो सकती है या समान मशीनों के समूह (फ्लेक्सिबल जॉब शॉप) से संबंधित हो सकती है।
• मशीनों को नौकरियों या निष्क्रिय समय के बीच एक निश्चित अंतराल की आवश्यकता हो सकती है।
• मशीनों में अनुक्रम-निर्भर सेटअप हो सकते हैं।
• ऑब्जेक्टिव फंक्शन मेकस्पैन को कम करने के लिए हो सकता है, एलपी स्पेस | एल_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$ मशीनों की संख्या है। ध्यान दें कि उपरोक्त परिभाषा के साथ, शेड्यूलिंग दक्षता केवल मशीनों की संख्या और कुल प्रसंस्करण समय के लिए सामान्यीकृत मेकस्पैन है। यह विभिन्न आकार के जेएसपी उदाहरणों में संसाधनों के उपयोग की तुलना करना संभव बनाता है।

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

JSP में जिन पहली समस्याओं से निपटा जाना चाहिए उनमें से एक यह है कि कई प्रस्तावित समाधानों की लागत अनंत है: यानी, मौजूद है $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: Multiprocessor scheduling

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

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

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

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

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

See also: Johnson's rule

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

जॉब पी_i P की अवधि के दो ऑपरेशन हैं_i1, पी_i2इसी क्रम में मशीन एम1, एम2 पर किया जाना है।

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

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

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

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

सूची ए से के को हटा दें; सूची L2 की शुरुआत में K जोड़ें।

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

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

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

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

मेकस्पैन भविष्यवाणी

मशीन लर्निंग का उपयोग हाल ही में इष्टतम शेड्यूल तैयार किए बिना जेएसपी उदाहरण के इष्टतम मेकस्पैन की भविष्यवाणी करने के लिए किया गया है।प्रारंभिक परिणाम लगभग 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