การจัดตารางงานแบบขนาน (เรียกอีกอย่างว่าการจัดตารางงานแบบขนาน^{[ 1 ] [ 2 ]}หรือการจัดตารางการประมวลผลแบบขนาน^{[ 3 ]} ) เป็นปัญหาการหาค่า เหมาะสมที่สุด ในวิทยาการคอมพิวเตอร์และการวิจัยการดำเนินงานเป็นรูปแบบหนึ่งของ การจัดตาราง งานที่เหมาะสมที่สุดในปัญหาการจัดตารางงานทั่วไป เราจะได้รับ งาน nงานJ , J , ..., J ที่มีเวลาการประมวลผลที่แตกต่างกัน ซึ่งจำเป็นต้องจัดตารางบน เครื่องจักร mเครื่อง ในขณะที่พยายามลดmakespan ให้เหลือน้อยที่สุด - ความยาวทั้งหมดของตาราง (นั่นคือ เมื่องานทั้งหมดเสร็จสิ้นการประมวลผล) ในรูปแบบเฉพาะที่เรียกว่าการจัดตารางงานแบบขนานเครื่องจักรทั้งหมดจะเหมือนกัน งานแต่ละงานjมีพารามิเตอร์ความยาวp และพารามิเตอร์ขนาดq และต้องทำงานเป็นเวลาp ขั้นตอนเวลาบน เครื่องจักร q เครื่องพร้อมกัน   

Veltman et al. ^{[ 4 ]}และ Drozdowski ^{[ 3 ]}ระบุปัญหานี้โดย${\displaystyle P|size_{j}|C_{\max }}$ในสัญกรณ์สามฟิลด์ที่แนะนำโดย Graham et al. ^{[ 5 ]} Pหมายความว่ามีเครื่องจักรที่เหมือนกันหลายเครื่องทำงานแบบขนานขนาดหมายความว่าแต่ละงานมีพารามิเตอร์ขนาดC หมายความว่าเป้าหมายคือการลดเวลาเสร็จสิ้นสูงสุดให้น้อยที่สุด ผู้เขียนบางคนใช้ ${\displaystyle P|m_{j}|C_{\max }}$แทนที่จะเป็นเช่นนั้น^{[ 1 ]}โปรดทราบว่าปัญหาของการจัดตารางเวลาเครื่องจักรคู่ขนานเป็นกรณีพิเศษของการจัดตารางเวลางานคู่ขนานที่${\displaystyle size_{j}=1}$สำหรับทุกค่าjกล่าวคือ งานแต่ละงานควรทำงานบนเครื่องเดียว

ที่มาของการกำหนดปัญหาดังกล่าวสามารถสืบย้อนไปได้ถึงปี พ.ศ. 2503 ^{[ 6 ]}สำหรับปัญหานี้ ไม่มีอัลกอริทึมการประมาณ ค่าแบบพหุนาม ที่มีอัตราส่วนน้อยกว่า${\displaystyle 3/2}$เว้นเสียแต่ว่า${\displaystyle P=NP}$[ ^{7 ]​}

มีชุดหนึ่ง${\displaystyle {\mathcal {J}}}$ของ${\displaystyle n}$งาน และ${\displaystyle m}$เครื่องจักรที่เหมือนกันทุกประการ งานแต่ละอย่าง${\displaystyle j\in {\mathcal {J}}}$มีเวลาในการประมวลผล${\displaystyle p_{j}\in \mathbb {N} }$(เรียกอีกอย่างว่าความยาวของj ) และต้องใช้พร้อมกันของ${\displaystyle q_{j}\in \mathbb {N} }$เครื่องจักรในระหว่างการดำเนินการ (เรียกอีกอย่างว่าขนาดหรือความกว้างของ j)

ตารางเวลาจะกำหนดงานแต่ละอย่างให้${\displaystyle j\in {\mathcal {J}}}$ถึงเวลาเริ่มต้น${\displaystyle s_{j}\in \mathbb {N} _{0}}$และชุดหนึ่ง${\displaystyle m_{j}\subseteq \{1,\dots ,m\}}$ของ${\displaystyle |m_{j}|=q_{j}}$เครื่องจักรที่จะใช้ในการประมวลผล ตารางการทำงานจะสามารถทำได้หากแต่ละโปรเซสเซอร์ทำงานไม่เกินหนึ่งงานในแต่ละครั้ง วัตถุประสงค์ของปัญหาแสดงโดย${\displaystyle P|size_{j}|C_{\max }}$คือการหาตารางเวลาที่มีระยะเวลาน้อยที่สุด${\displaystyle C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})}$หรือเรียกอีกอย่างว่า makespan ของตารางงาน เงื่อนไขที่เพียงพอสำหรับความเป็นไปได้ของตารางงานมีดังต่อไปนี้

${\displaystyle \sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}}$.

หากคุณสมบัตินี้เป็นไปตามเงื่อนไขสำหรับเวลาเริ่มต้นทั้งหมด จะสามารถสร้างตารางงานที่เป็นไปได้โดยการจัดสรรเครื่องจักรว่างให้กับงานในแต่ละเวลา โดยเริ่มจากเวลาที่กำหนด${\displaystyle t=0}$[ ^{1 ] [ 2 ]}นอกจากนี้ จำนวนช่วงเวลาของเครื่องจักรที่ใช้โดยงานและช่วงเวลาว่างในแต่ละขั้นตอนเวลาสามารถจำกัดได้^ด้วย${\displaystyle |{\mathcal {J}}|+1}$[ ^{1 ] ในที่นี้ ช่วงเครื่องจักรคือเซตของเครื่องจักรที่ต่อเนื่องกันที่มีจำนวนสมาชิกสูงสุด โดยที่เครื่องจักรทั้งหมดในเซตนี้กำลัง ประมวล}ผลงานเดียวกัน ช่วงเครื่องจักรจะถูกระบุอย่างสมบูรณ์โดยดัชนีของเครื่องจักรเครื่องแรกและเครื่องสุดท้าย ดังนั้นจึงเป็นไปได้ที่จะได้วิธีการเข้ารหัสเอาต์พุตที่กระชับด้วยขนาดพหุนาม

ปัญหานี้เป็นปัญหา NP-hard แม้ว่าจะมีเครื่องจักรเพียงสองเครื่องและขนาดของงานทั้งหมดเป็นค่าคงที่ก็ตาม${\displaystyle q_{j}=1}$(กล่าวคือ แต่ละงานจะต้องทำงานบนเครื่องเดียวเท่านั้น) กรณีพิเศษนี้ จะแสดงด้วย${\displaystyle P2||C_{\max }}$เป็นรูปแบบหนึ่งของปัญหาการแบ่งส่วนซึ่งเป็นที่ทราบกันดีว่าเป็นปัญหา NP-hard

เมื่อจำนวนเครื่องจักรmมีค่าไม่เกิน 3 นั่นคือ สำหรับตัวแปรต่างๆ${\displaystyle P2|size_{j}|C_{\max }}$และ${\displaystyle P3|size_{j}|C_{\max }}$มี อัลกอริทึม เวลาพсевдоพหุนามซึ่งแก้ปัญหาได้อย่างแม่นยำ^{[ 8 ]}

ในทางตรงกันข้าม เมื่อจำนวนเครื่องจักรมีอย่างน้อย 4 เครื่อง นั่นคือ สำหรับตัวแปรต่างๆ${\displaystyle Pm|size_{j}|C_{\max }}$สำหรับใดๆ${\displaystyle m\geq 4}$ปัญหานี้ยังเป็นปัญหาNP-hard อย่างมาก อีกด้วย ^{[ 9 ]} (ผลลัพธ์นี้ปรับปรุงผลลัพธ์ก่อนหน้า^{[ 8 ]}ที่แสดงให้เห็นถึงความยากของ NP-hard อย่างมากสำหรับ${\displaystyle m\geq 5}$)

หากจำนวนเครื่องจักรไม่ได้ถูกจำกัดด้วยค่าคงที่ จะไม่มีอัลกอริทึมการประมาณค่าใดที่มีอัตราส่วนการประมาณค่าน้อยกว่า${\displaystyle 3/2}$เว้นเสียแต่ว่า${\displaystyle P=NP}$หลักการนี้ยังคงใช้ได้แม้ในกรณีพิเศษที่เวลาในการประมวลผลของงานทั้งหมดคือ${\displaystyle p_{j}=1}$เนื่องจากกรณีพิเศษนี้เทียบเท่ากับปัญหาการบรรจุลงถัง : แต่ละช่วงเวลาสอดคล้องกับถังหนึ่งใบ, m คือขนาด ถัง, แต่ละงานสอดคล้องกับสิ่งของที่มีขนาดqjและการลดระยะเวลาการผลิตให้เหลือน้อยที่สุดนั้นสอดคล้องกับการลดจำนวนถังให้เหลือน้อยที่สุด

มีการศึกษาปัญหาหลายรูปแบบ^{[ 3 ]}นอกจากนี้ยังมีการพิจารณารูปแบบต่างๆ ต่อไปนี้ร่วมกันด้วย

ข้อจำกัดด้านลำดับความสำคัญ : ในรูปแบบนี้ จะมีความสัมพันธ์ด้านลำดับความสำคัญระหว่างงานต่างๆ ตัวอย่างเช่น หากงานสองงานiและjมีความสัมพันธ์ด้านลำดับความสำคัญที่iต้องมาก่อนjกล่าวคือ${\displaystyle i\prec j}$ดังนั้นiจะต้องอยู่ก่อนjในวิธีแก้ปัญหาที่เป็นไปได้ใดๆ ปัญหานี้เป็นปัญหา NP-hard (การลดรูปโดยใช้คลิก ) แม้ว่าเวลาประมวลผลทั้งหมดจะถูก นำไปใช้แล้วก็ตาม${\displaystyle p_{j}}$มีค่าเท่ากันสำหรับ เครื่องจักร mเครื่อง อย่างไรก็ตาม เราสามารถแก้ปัญหาสำหรับเครื่องจักร 2 เครื่องได้ในเวลาพหุนาม เนื่องจากปัญหาที่แท้จริงคือการค้นหาการจับคู่ที่สมบูรณ์แบบที่มีความยาวระดับหนึ่ง ในกรณีที่ไม่มีการจับคู่ที่สมบูรณ์แบบสำหรับงานสองงาน ณ เวลาใดเวลาหนึ่ง (ซึ่งอาจเป็นเพราะไม่มีงานว่าง ณ เวลานั้น) เราอาจเพิ่มงานจำลองเพื่อความถูกต้อง การหาความซับซ้อนในการคำนวณสำหรับ${\displaystyle P3|}$พรีค${\displaystyle |C_{max}}$อย่างไรก็ตาม ยังไม่เป็นที่ทราบแน่ชัด^{[ 10 ]}

งานต่อเนื่อง : ในรูปแบบนี้ เครื่องจักรจะมีลำดับการทำงานที่แน่นอน${\displaystyle (M_{1},\dots ,M_{m})}$แทนที่จะมอบหมายงานให้กับกลุ่มย่อยใดกลุ่มหนึ่ง${\displaystyle m_{j}\subseteq \{M_{1},\dots ,M_{m}\}}$งานต่างๆ จะต้องถูกจัดสรรให้กับช่วงเครื่องจักรที่ต่อเนื่องกัน ปัญหานี้สอดคล้องกับการกำหนดปัญหาของการบรรจุแบบแถบ (strip packing problem )

หลายแพลตฟอร์ม:ในรูปแบบนี้ ชุดของเครื่องจะถูกแบ่งออกเป็นแพลตฟอร์มอิสระ งานที่กำหนดไว้ล่วงหน้าสามารถใช้เครื่องของแพลตฟอร์มเดียวเท่านั้น และไม่อนุญาตให้ประมวลผลข้ามหลายแพลตฟอร์ม

งานที่ปรับเปลี่ยนได้ : ในรูปแบบนี้ งานแต่ละอย่าง${\displaystyle j\in {\mathcal {J}}}$มีชุดจำนวนเครื่องจักรที่เป็นไปได้${\displaystyle D_{j}\subseteq \{1,\dots m\}}$สำหรับการนับแต่ละครั้ง${\displaystyle d\in D_{j}}$งานดังกล่าวสามารถประมวลผลบน เครื่อง dเครื่องพร้อมกันได้ และในกรณีนี้ เวลาในการประมวลผลจะเป็น${\displaystyle p_{j,d}}$เพื่อกำหนดตารางงาน${\displaystyle j\in {\mathcal {J}}}$อัลกอริทึมจะต้องเลือกจำนวนเครื่องจักร${\displaystyle d\in D_{j}}$และกำหนดjให้เป็นเวลาเริ่มต้น${\displaystyle s_{j}}$และถึง${\displaystyle d}$เครื่องจักรในช่วงเวลาดังกล่าว${\displaystyle [s_{j},s_{j}+p_{j,d}).}$ โดยทั่วไปแล้ว ข้อสันนิษฐานสำหรับปัญหาประเภทนี้คือ ปริมาณงานทั้งหมดของงาน ซึ่งกำหนดไว้ดังนี้${\displaystyle d\cdot p_{j,d}}$ค่าจะไม่เพิ่มขึ้นเมื่อจำนวนเครื่องจักรเพิ่มขึ้น

วันวางจำหน่าย : ในเวอร์ชันนี้ ระบุโดย${\displaystyle P|size_{j},r_{j}|C_{\max }}$ไม่ใช่ว่างานทั้งหมดจะพร้อมใช้งาน ณ เวลา 0; งานแต่ละงานjจะพร้อมใช้งาน ณ เวลาr ที่แน่นอนและทราบได้ และจะต้องกำหนดตารางเวลาหลังจากเวลานั้น

การแย่งชิงสิทธิ์ : ในรูปแบบนี้ จะแสดงด้วย${\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }}$สามารถขัดจังหวะงานที่กำลังทำงานอยู่ และกำหนดเวลาสำหรับงานอื่นๆ ที่พร้อมใช้งานในเวลานั้นได้

อัลกอริทึมการจัดตารางเวลารายการโดย Garey และ Graham ^{[ 11 ]}มีอัตราส่วนสัมบูรณ์${\displaystyle 2}$ตามที่ Turek et al. ^{[ 12 ]}และ Ludwig และ Tiwari ^{[ 13 ]} ชี้ให้เห็น Feldmann, Sgall และ Teng ^{[ 14 ]}สังเกตว่าความยาวของตารางเวลาที่ไม่สามารถแทรกแซงได้ซึ่งสร้างขึ้นโดยอัลกอริทึมการจัดตารางเวลารายการนั้นมีค่าสูงสุดเพียงเท่านั้น${\displaystyle (2-1/m)}$คูณด้วยระยะเวลาการผลิตที่เหมาะสมที่สุดก่อนการแทรกแซง แผนการประมาณค่าแบบพหุนามเวลา (PTAS) สำหรับกรณีที่จำนวน${\displaystyle m}$จำนวนโปรเซสเซอร์คงที่ ซึ่งแสดงด้วย${\displaystyle Pm|size_{j}|C_{\max }}$นำเสนอโดย Amoura et al. ^{[ 15 ]}และ Jansen et al. ^{[ 16 ]} ต่อมา Jansen และ Thöle ^{[ 2 ]}พบ PTAS สำหรับกรณีที่จำนวนโปรเซสเซอร์ถูกจำกัดด้วยพหุนามในจำนวนงาน ในอัลกอริทึมนี้ จำนวนเครื่องจะปรากฏเป็นพหุนามในความซับซ้อนของเวลาของอัลกอริทึม เนื่องจากโดยทั่วไปแล้ว จำนวนเครื่องจะปรากฏเป็นลอการิทึมในขนาดของอินสแตนซ์เท่านั้น อัลกอริทึมนี้จึงเป็นแบบแผนการประมาณเวลาแบบพหุนามเทียมเช่นกัน${\displaystyle (3/2+\varepsilon )}$-การประมาณค่าได้รับจาก Jansen ^{[ 17 ]}ซึ่งปิดช่องว่างไปยังขอบล่างของ${\displaystyle 3/2}$ยกเว้นในกรณีที่เล็กมากโดยพลการ${\displaystyle \varepsilon }$.

เมื่อพิจารณาตัวอย่างของปัญหาการจัดตารางงานแบบขนาน ระยะเวลาการผลิตที่เหมาะสมที่สุดอาจแตกต่างกันไปขึ้นอยู่กับข้อจำกัดเรื่องความต่อเนื่องของเครื่องจักร หากสามารถจัดตารางงานบนเครื่องจักรที่ไม่ต่อเนื่องกันได้ ระยะเวลาการผลิตที่เหมาะสมที่สุดอาจน้อยกว่าในกรณีที่ต้องจัดตารางงานบนเครื่องจักรที่ต่อเนื่องกัน ความแตกต่างระหว่างตารางงานที่ต่อเนื่องและไม่ต่อเนื่องกันได้รับการสาธิตครั้งแรกในปี 1992 ^{[ 18 ]}ในตัวอย่างที่มี${\displaystyle n=8}$ งานต่างๆ${\displaystyle m=23}$โปรเซสเซอร์${\displaystyle C_{\max }^{nc}=17}$, และ${\displaystyle C_{\max }^{c}=18}$Błądek และคณะ^{[ 19 ]}ศึกษาความแตกต่างที่เรียกว่า c/nc เหล่านี้และพิสูจน์ประเด็นต่อไปนี้:

• เพื่อให้เกิดความแตกต่างระหว่าง ac/nc จะต้องมีงานอย่างน้อยสามงานด้วยกัน${\displaystyle q_{j}>1.}$
• เพื่อให้เกิดความแตกต่างระหว่าง ac/nc จะต้องมีงานอย่างน้อยสามงานด้วยกัน ${\displaystyle p_{j}>1.}$
• เพื่อให้เกิดความแตกต่างระหว่างกระแสสลับและกระแสตรง อย่างน้อยที่สุด${\displaystyle m=4}$จำเป็นต้องใช้โปรเซสเซอร์ (และมีกรณีหนึ่งที่มีความแตกต่างระหว่างกระแสสลับและกระแสตรง)${\displaystyle m=4}$)
• เพื่อให้เกิดความแตกต่างระหว่าง ac/nc ความยาวของตารางเวลาที่ไม่ต่อเนื่องจะต้องมีอย่างน้อย${\displaystyle C_{\max }^{nc}=4.}$
• ความแตกต่าง c/nc สูงสุด${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)}$อย่างน้อยก็${\displaystyle 5/4}$และอย่างมากที่สุด${\displaystyle 2.}$
• การตัดสินใจว่ามีความแตกต่างระหว่าง c/nc ในกรณีใดกรณีหนึ่งหรือไม่นั้นเป็นปัญหา NP-complete

นอกจากนี้ พวกเขายังเสนอข้อสันนิษฐานสองข้อต่อไปนี้ ซึ่งยังไม่ได้รับการพิสูจน์:

• เพื่อให้เกิดความแตกต่างระหว่างกระแสสลับและกระแสตรง อย่างน้อยที่สุด${\displaystyle n=7}$จำเป็นต้องมีภารกิจต่างๆ
• ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}$

มีปัญหาการจัดตารางงานที่เกี่ยวข้องซึ่งแต่ละงานประกอบด้วยการดำเนินงานหลายอย่างที่ต้องดำเนินการตามลำดับ (แทนที่จะเป็นแบบขนาน) ปัญหาเหล่านี้ได้แก่ ปัญหา การจัดตารางงาน แบบโรงงานเปิด (open shop scheduling) ปัญหาการจัดตารางงาน แบบโรงงานไหล ( flow shop scheduling ) และปัญหาการจัดตารางงานแบบโรงงานสั่งทำ (job shop scheduling )