नौकरी-दुकान का शेड्यूल

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

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

समस्या विविधताएँ

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

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

एनपी-कठोरता

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

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

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

होने देना $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: Multiprocessor scheduling

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

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

एकाधिक परिचालनों से युक्त नौकरियां

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

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

See also: Johnson's rule

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

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

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

यदि न्यूनतम P का है_k1,

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

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

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

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

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

विचार इस प्रकार है: कल्पना करें कि प्रत्येक कार्य के लिए एम1, एम2…एमएम पर क्रम में एम संचालन की आवश्यकता होती है। हम पहली 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