आर

Question

में कार्य शेड्यूलिंग या बिन-पैकिंग अनुकूलन को हल करना मेरे पास अनुकूलन समस्या है। यह ऐसे उत्पाद के बारे में है जिसमें 20 भाग होते हैं (उत्पादन का आदेश कोई फर्क नहीं पड़ता)। मुझे 3 समान मशीन मिल गई हैं जो सभी 20 भागों का उत्पादन कर सकती हैं।

मैं 20 भागों मिनट में प्रतिनिधित्व (यानी। यह 3min लेता है पहले भाग और 75min का उत्पादन करने के दूसरे भाग का उत्पादन करने, आदि)

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48) 

मिल गया है तो 1 उत्पाद का निर्माण करने के लिए इसे 730 लेता है मि।

sum(ItemTime) 

इसका लक्ष्य तीन वस्तुओं को अच्छी वस्तु आवंटित करके एक उत्पाद के उत्पादन को कम करना है।

sum(ItemTime/3) 

तो वास्तव में मैं 243.333 मिनट (730/3) के रूप में के रूप में पास होने की जरूरत है

संभावना की राशि विशाल 3^20

मुझे लगता है कि कई अलग अलग इष्टतम समाधान देखते हैं है। मैं चाहता हूं कि आर मुझे उन सभी को दे। मुझे केवल कुल समय जानने की आवश्यकता नहीं है जिसके लिए मशीन 1 2 और 3 की आवश्यकता होगी: मुझे यह भी पता होना चाहिए कि मशीन 1 को मशीन 2 और मशीन के लिए कौन सा आइटम देना है।

वैकल्पिक रूप से, यदि यह बहुत लंबा है मैं पुनरावृत्ति के बिना नमूना चुनना चाहता हूं जो यथासंभव उचित है ...

क्या मैं अपनी समस्या को आर भाषा के साथ हल कर सकता हूं?

Answer 1

मेरा मानना ​​है कि आपकी समस्या एकाधिक नेप्सेक समस्या (MKP) जो, एक प्रायोरी, नहीं एक केक का टुकड़ा की एक करीबी विविधता है ...

हालांकि, आपका आयाम इतना छोटा है कि समस्या को मिश्रित-इंटीजर प्रोग्रामिंग (एमआईपी) के रूप में हल किया जा सकता है। मैंने इसे Rglpk का उपयोग करके नीचे हल किया; यह लगभग चार मिनट हलचल ले लिया। यदि आप सीपीएलईएक्स तक पहुंचने के लिए भाग्यशाली हैं, तो मैं आपको सलाह देता हूं कि आप Rcplex का उपयोग करें, यह इसे धुआं देगा।

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48) 
N <- length(ItemTime) 
M <- 3 

समस्या सूत्रीकरण:

# variables are in this order: 
# z: slack variable for the max of (s1, s2, s3) 
# s1: sum of times for machine 1 
# s2: sum of times for machine 2 
# s3: sum of times for machine 3 
# a1-a20: booleans for assignment to machine1 
# b1-b20: booleans for assignment to machine1 
# c1-c20: booleans for assignment to machine1 

obj <- c(1, rep(0, 3 + 3*N)) 

mat <- rbind(
    c(1, -1, 0, 0, rep(0, M*N)),      # z >= s1 
    c(1, 0, -1, 0, rep(0, M*N)),      # z >= s2 
    c(1, 0, 0, -1, rep(0, M*N)),      # z >= s3 
    c(0, -1, 0, 0, ItemTime, rep(0, N), rep(0, N)), # s1 = ... 
    c(0, 0, -1, 0, rep(0, N), ItemTime, rep(0, N)), # s2 = ... 
    c(0, 0, 0, -1, rep(0, N), rep(0, N), ItemTime), # s3 = ... 
    cbind(matrix(0, N, 4), diag(N), diag(N), diag(N)) # a_i + b_i + c_i = 1 
) 

dir <- c(">=", ">=", ">=", "==", "==", "==" , rep("==", N)) 

rhs <- c(rep(0, 2*M), rep(1, N)) 

types <- c(rep("C", 1+M), rep("B", M*N)) 

अब चलो इसे हल करते हैं:

Rglpk_solve_LP(obj, mat, dir, rhs, types, max=FALSE, verbose=TRUE) 

# GLPK Simplex Optimizer, v4.47 
# INTEGER OPTIMAL SOLUTION FOUND 
# $optimum 
# [1] 244 
# 
# $solution 
# [1] 244 243 243 244 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 
# [31] 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 
# [61] 0 0 0 1 
# 
# $status 
# [1] 0 

Answer 2

संपादित: जाहिर है इस समस्या, मुझे याद करने के लिए एक थोड़ा अलग है क्योंकि जैसा कि @han शो, इस एल्गोरिथ्म (इष्टतम नहीं, केवल एक सन्निकटन है, यद्यपि वहाँ एक गारंटी इस एल्गोरिथ्म से "makespan" है सामान्य रूप से 4/3 * इष्टतम बदलाव से अधिक नहीं और 3 मशीनों के लिए 11/9 * इष्टतम।)।

लिंक @han प्रदान किया गया लिंक the multiprocessor scheduling article से जुड़ा हुआ है, जो इस समस्या के बराबर है। लेख हमें बताता है कि समस्या वास्तव में एनपी-हार्ड है। जिसका अर्थ है कि इष्टतम उत्तर की गणना करने के लिए कोई बहुपद समय एल्गोरिदम नहीं है (हमारे पास बहुत कम O(n log n) है)।

---

तुम सिर्फ एक लालची एल्गोरिथ्म का उपयोग कर सकते हैं: सूची के माध्यम से जाने के लिए और काम है कि मशीन वर्तमान में कम से कम काम यह करने के लिए आवंटित किया है कि करने के लिए सबसे लंबे समय तक ले जाता है आवंटित।

उदाहरण के तौर पर, अपने भाग विनिर्माण समय के रूप में केवल c(5,3,6,1,2) पर विचार करें। सबसे पहले आप इसे घटते क्रम में क्रमबद्ध करें: c(6,5,3,2,1), और उसके बाद कार्यों को असाइन करने के क्रम में (क्रम में) जाएं।

 Step: 1 2 3 4 5 
Machine 1: 6 6 6 6 6 
Machine 2: - 5 5 5 5,1 
Machine 3: - - 3 3,2 3,2 

तो मशीन 1 बात यह है कि 6 मिनट लगते हैं बनाता है, मशीन 2 जो कि 1 से 5 मिनट लेने के लिए और मशीन 3 एक है कि लेता है बनाता है बनाता है 3 और 2

आप देख सकते हैं कि में चरण 4, सबसे कम कुल समय वाली मशीन मशीन 3 है इसलिए हमने 2 को असाइन किया है।

स्मृति से, इस एल्गोरिथ्म वास्तव में सर्वोत्तम है, हालांकि मेरे पास उस दावे के लिए कोई लिंक नहीं है। मैं भी अगर आप इसे अनुकूलित सभी संभव इष्टतम परिणाम प्राप्त कर सकते पता नहीं है।

---

आप एक समारोह है कि एक काम और उनकी वर्तमान नौकरियों के साथ मशीनों की एक सूची लेता है परिभाषित हैं, तो आप Reduce उपयोग करने वाले सभी काम देना कर सकते हैं। एकल कार्य असाइनमेंट कुछ लग सकता है जैसे:

assign.job <- function(machines, job) { 
    which.machines <- which.min(lapply(machines, sum)) 
    machines[[which.machines]] <- c(machines[[which.machines]], job) 
    machines 
} 

(मैं machines[[which.machines]] लाइन पसंद नहीं है ... मुझे यकीन है कि वहाँ एक विशिष्ट सूचकांक एक सूची को संशोधित करने के लिए एक बेहतर तरीका है कर रहा हूँ।)

और फिर काम की तरह हो सकता है:

allocate <- function(num.machines, job.times) { 
    machines <- lapply(1:num.machines, function(...) c()) 
    Reduce(assign.job, 
      sort(job.times, decreasing=TRUE), 
      machines) 
} 

(मैं लाइन है कि machines <- शुरू होता है पसंद नहीं है: मुझे यकीन है कि वहाँ लंबाई n की एक सूची बनाने का एक neater तरीका है हूँ, लेकिन मैं नहीं कर सकता इसे ढूंढें।)

,210

अपने उदाहरण पर, यह देता है:

> allocate(3,ItemTime) 
[[1]] 
[1] 84 58 46 45 8 3  # total time: 244 

[[2]] 
[1] 84 55 55 21 16 8 5 # total time: 244 

[[3]] 
[1] 75 65 48 28 12 11 3 # total time: 242 

अंतिम चरण बाहर काम कर रहा है जो काम है जो समय से मेल खाती है: यह या तो बार बताए के बाद पीछे की ओर काम कर रहा द्वारा किया जा सकता है (यह लगभग रैखिक में किया जा सकता समय के बाद से वहाँ नौकरी और ठीक इसके विपरीत) करने के लिए समय से या allocate और assign.job संशोधित नौकरियों के सूचकांक का ट्रैक रखने के (यदि आप तो order समारोह और अधिक उपयोगी हो जाएगा यह करने के लिए जा रहे हैं द्वारा एक अपेक्षाकृत सरल मानचित्रण है sort से, और वैक्टरों के बजाय डेटाफ्रेम का उपयोग करके, एक कॉलम में समय और अन्य में इंडेक्स स्टोर करने के लिए)।

(ऐसा लगता है कि इस समाधान, कई बार अन्य की तुलना में तेजी है, क्योंकि अन्य जवाब उच्च शक्ति एल्गोरिदम, जो इस समस्या के लिए संभवतः overkill नहीं हैं ... "संभवतः" क्योंकि मैं उपयोग कर रहा है मीटर अभी भी नहीं 100% यकीन है कि यह एल्गोरिथ्म इष्टतम है।)

Answer 3

अन्य उत्तर में बताया गया है इस bin packing problem से संबंधित है। एक साधारण बिन पैकिंग एल्गोरिदम पहले से ही BBmisc पैकेज में लागू किया गया है; हम एक सरल और तेजी से समाधान के लिए यहाँ इस मौजूदा समारोह लागू कर सकते हैं:

library(BBmisc) 

binlimit <- 3 # specify how many bins 
binsize <- ceiling(sum(ItemTime)/binlimit) # calculate the minimum possible bin size (244) 
binPack(ItemTime, binsize) # pack the bins 

[1] 3 1 2 3 3 2 2 3 3 3 2 3 1 3 2 3 3 1 3 3 

इस मामले में, यह तुरंत सर्वोत्कृष्ट समाधान 3 डिब्बे का उपयोग कर उत्पादन करता है।हम समाधान के बिन आकार की पुष्टि कर सकते हैं:

library(dplyr) 
df <- data.frame(ItemTime, bins) 
df %>% group_by(bins) %>% summarise (time = sum(ItemTime)) 

    bins time 
1 1 243 
2 2 244 
3 3 243 

तो binPack एक प्रारंभिक समाधान भी कई डिब्बे का उपयोग कर पैदा करता है, उस में रखा जा सकता है एक के लिए लूप कि binsize वृद्धि कर देता है और केवल एक समाधान देता है जब वहाँ से अधिक नहीं कर रहे हैं binPack के आउटपुट में 3 डिब्बे।

दिलचस्प बात यह है binPack ऊपर flodel के जवाब के रूप में ही बिन आकार के साथ एक समाधान देता है, लेकिन डिब्बे 2 और 3 में विभिन्न कार्य के साथ:

ItemTime Rglpk binPack 
1   3  3  3 
2  75  1  1 
3  55  2  2 
4  12  2  3 
5  45  3  3 
6  55  3  2 
7  11  2  2 
8   8  2  3 
9  21  2  3 
10  16  3  3 
11  65  2  2 
12  28  3  3 
13  84  1  1 
14  3  3  3 
15  58  2  2 
16  46  3  3 
17  5  2  3 
18  84  1  1 
19  8  2  3 
20  48  3  3 

binPack इस समस्या को हल करने के लिए एक तेज और आसान तरीका प्रदान करता है, इसके विवरण लिखते हैं कि इस एल्गोरिथ्म सरल है और इष्टतम समाधान वापस नहीं कर सकते: राशि कम या क्षमता की तुलना में बराबर के साथ समूहों में

मैप्स एक्स में संख्यात्मक आइटम नहीं है। एक बहुत ही सरल लालची एल्गोरिदम का उपयोग किया जाता है, जो वास्तव में गति के लिए अनुकूलित नहीं है। यह छोटे वैक्टर के लिए एक सुविधाजनक कार्य है, वास्तविक बिनबैकिंग समस्या के लिए प्रतिस्पर्धात्मक सॉल्वर नहीं। यदि एक्स का एक तत्व क्षमता से अधिक है, तो एक त्रुटि फेंक दी जाती है।