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

มีปัญหาการจัดตารางงานที่เหมาะสมที่สุดมากมาย ซึ่งแตกต่างกันในลักษณะของงาน ลักษณะของเครื่องจักร ข้อจำกัดในการจัดตาราง และฟังก์ชันเป้าหมายRonald Graham , Eugene Lawler , Jan Karel LenstraและAlexander Rinnooy Kanได้นำเสนอสัญกรณ์ ที่สะดวกสำหรับปัญหาการจัดตารางงานที่เหมาะสมที่สุด ^{[ 1 ] [ 2 ]} สัญกรณ์ นี้ประกอบด้วยสามส่วน ได้แก่α , βและγแต่ละส่วนอาจเป็นรายการคำที่คั่นด้วยเครื่องหมายจุลภาค ส่วน α อธิบายสภาพแวดล้อมของเครื่องจักร β อธิบายลักษณะและข้อจำกัดของงาน และ γ อธิบายฟังก์ชันเป้าหมาย^{[ 3 ]}นับตั้งแต่มีการนำเสนอในปลายทศวรรษ 1970 สัญกรณ์นี้ได้รับการขยายอย่างต่อเนื่อง บางครั้งก็ไม่สอดคล้องกัน ส่งผลให้ในปัจจุบันมีปัญหาบางอย่างที่ปรากฏพร้อมสัญกรณ์ที่แตกต่างกันในเอกสารหลายฉบับ

ในปัญหาการจัดตารางงานที่เหมาะสมที่สุดแบบง่ายๆ งานแต่ละงานjจะประกอบด้วยขั้นตอนการดำเนินการเพียงขั้นตอนเดียว โดยมีเวลาประมวลผลที่กำหนดไว้p ในรูปแบบที่ซับซ้อนกว่านั้น งานแต่ละงานจะประกอบด้วยขั้นตอนการดำเนินการหลายขั้นตอน ซึ่งอาจดำเนินการตามลำดับหรือพร้อมกันก็ได้

ในปัญหาการจัดตารางงานแบบขั้นตอนเดียวมีสภาพแวดล้อมของเครื่องจักรหลักๆ สี่ประเภท:

• 1 : การจัดตารางงานสำหรับเครื่องจักรเดี่ยวมีเครื่องจักรเพียงเครื่องเดียว
• P : การจัดตารางเวลาเครื่องจักรที่เหมือนกันมีอยู่${\displaystyle m}$เครื่องจักรคู่ขนาน และเครื่องจักรเหล่านั้นเหมือนกันทุกประการ งาน${\displaystyle j}$ต้องใช้เวลา${\displaystyle p_{j}}$บนเครื่องใดก็ได้ที่กำหนดไว้
• ถาม : การจัดตารางงานเครื่องจักรแบบเดียวกันมีอยู่กี่แบบ${\displaystyle m}$เครื่องจักรคู่ขนาน และมีอัตราเร็วที่กำหนดแตกต่างกัน งาน${\displaystyle j}$บนเครื่อง${\displaystyle i}$ต้องใช้เวลา${\displaystyle p_{j}/s_{i}}$.
• R : การจัดตารางเวลาเครื่องจักรที่ไม่เกี่ยวข้องกันมีอยู่${\displaystyle m}$เครื่องจักรคู่ขนาน และไม่มีความเกี่ยวข้องกัน – จ็อบ${\displaystyle j}$บนเครื่อง${\displaystyle i}$ต้องใช้เวลา${\displaystyle p_{ij}}$.

ตัวอักษรเหล่านี้อาจตามด้วยจำนวนเครื่องจักร ซึ่งเป็นค่าคงที่ ตัวอย่างเช่นP2แสดงว่ามีเครื่องจักรคู่ขนานที่เหมือนกันสองเครื่องPmแสดงว่ามีเครื่องจักรคู่ขนานที่เหมือนกันm เครื่อง โดยที่ mเป็นพารามิเตอร์คงที่ ในทางตรงกันข้ามPแสดงว่ามี เครื่องจักรคู่ขนานที่เหมือนกัน m เครื่องแต่mไม่ได้ถูกกำหนดตายตัว (เป็นส่วนหนึ่งของข้อมูลป้อนเข้า)

ในปัญหาการจัดตารางงานแบบหลายขั้นตอนมีตัวเลือกอื่นๆ สำหรับสภาพแวดล้อมของเครื่องจักร:

• O : ปัญหาการเปิดร้านค้าทุกงาน${\displaystyle j}$ประกอบด้วย${\displaystyle m}$การดำเนินงาน${\displaystyle O_{ij}}$สำหรับ${\displaystyle i=1,\ldots ,m}$สามารถกำหนดลำดับการดำเนินการได้ตามต้องการการดำเนินการ${\displaystyle O_{ij}}$ต้องดำเนินการสำหรับ${\displaystyle p_{ij}}$หน่วยบนเครื่องจักร${\displaystyle i}$.
• F : ปัญหาการผลิตแบบ Flow-shopทุกงาน${\displaystyle j}$ประกอบด้วย${\displaystyle m}$การดำเนินงาน${\displaystyle O_{ij}}$สำหรับ${\displaystyle i=1,\ldots ,m}$โดยจะจัดลำดับตามที่ระบุไว้การดำเนินการ${\displaystyle O_{ij}}$ต้องดำเนินการสำหรับ${\displaystyle p_{ij}}$หน่วยบนเครื่องจักร${\displaystyle i}$.
• J : ปัญหาโรงงานผลิตสินค้าตามสั่งทุกงาน${\displaystyle j}$ประกอบด้วย${\displaystyle n_{j}}$การดำเนินงาน${\displaystyle O_{kj}}$สำหรับ${\displaystyle k=1,\ldots ,n_{j}}$โดยจะกำหนดตารางเวลาตามลำดับนั้น ปฏิบัติการ${\displaystyle O_{kj}}$ต้องดำเนินการสำหรับ${\displaystyle p_{kj}}$หน่วยบนเครื่องจักรเฉพาะ${\displaystyle \mu _{kj}}$กับ${\displaystyle \mu _{kj}\neq \mu _{k'j}}$สำหรับ${\displaystyle k\neq k'}$.

โดยทั่วไปแล้ว เวลาในการประมวลผลทั้งหมดจะถือว่าเป็นจำนวนเต็ม อย่างไรก็ตาม ในเอกสารงานวิจัยเก่าบางฉบับ ถือว่าเป็นจำนวนตรรกยะ

• ${\displaystyle p_{i}=p}$, หรือ${\displaystyle p_{ij}=p}$: ระยะเวลาในการประมวลผลเท่ากันสำหรับทุกงาน
• ${\displaystyle p_{i}=1}$, หรือ${\displaystyle p_{ij}=1}$: เวลาในการประมวลผลเท่ากับ 1 หน่วยเวลาสำหรับงานทั้งหมด
• ${\displaystyle r_{j}}$: สำหรับแต่ละงาน จะมีการกำหนดเวลาปล่อยงาน ซึ่งจะไม่สามารถกำหนดเวลาทำงานได้ก่อนเวลานั้น โดยค่าเริ่มต้นคือ 0
• ${\displaystyle {\text{online-}}r_{j}}$: ปัญหาที่เกิดขึ้นในระบบออนไลน์ งานต่างๆ จะปรากฏขึ้นตามเวลาที่ประกาศ ดูข้อมูลเพิ่มเติมได้ที่ การ จัดตารางงานออนไลน์
• ${\displaystyle d_{j}}$: สำหรับแต่ละงานจะมีกำหนดส่งงาน แนวคิดคือทุกงานควรเสร็จก่อนกำหนดส่ง และจะมีบทลงโทษสำหรับงานที่เสร็จช้ากว่ากำหนด บทลงโทษนี้จะแสดงอยู่ในค่าเป้าหมาย การมีอยู่ของลักษณะงาน${\displaystyle d_{j}}$โดยปริยายจะถือว่าเข้าใจอยู่แล้วและไม่ได้ระบุไว้ในชื่อของปัญหา เว้นแต่จะมีข้อจำกัดบางประการ เช่น${\displaystyle d_{j}=d}$โดยสมมติว่าวันครบกำหนดทั้งหมดเท่ากับวันที่กำหนดไว้
• ${\displaystyle {\bar {d}__{j}}$: แต่ละงานจะมีกำหนดเวลาที่แน่นอน ทุกงานต้องเสร็จก่อนกำหนดเวลา
• pmtn : งานสามารถถูกขัดจังหวะและกลับมาดำเนินการต่อได้บนเครื่องอื่น บางครั้งอาจใช้สัญลักษณ์ ' prmp' แทน'.
• ${\displaystyle {\text{size}}_{j}}$แต่ละงานจะมีจำนวนเครื่องจักรที่ต้องจัดตารางการทำงานพร้อมกัน โดยค่าเริ่มต้นคือ 1 พารามิเตอร์นี้มีความสำคัญในรูปแบบที่เรียกว่าการจัดตารางงานแบบขนาน (parallel task scheduling )

โดยทั่วไปเป้าหมายคือการลดค่าวัตถุประสงค์บางอย่างให้เหลือน้อยที่สุด ความแตกต่างอย่างหนึ่งคือสัญลักษณ์ที่ใช้${\displaystyle \sum U_{j}}$โดยมีเป้าหมายคือการเพิ่มจำนวนงานที่เสร็จสมบูรณ์ก่อนกำหนดให้ได้มากที่สุด ซึ่งเรียกอีกอย่างว่าอัตราผลผลิต (throughput ) ค่าเป้าหมายอาจเป็นผลรวม หรืออาจมีการถ่วงน้ำหนักด้วยค่าลำดับความสำคัญที่กำหนดไว้${\displaystyle w_{j}}$ต่อหนึ่งงาน

• - : การไม่มีค่าเป้าหมายจะแสดงด้วยขีดเดี่ยว ซึ่งหมายความว่าปัญหาประกอบด้วยการสร้างตารางเวลาที่เป็นไปได้ซึ่งสอดคล้องกับข้อจำกัดที่กำหนดทั้งหมดเท่านั้น
• ${\displaystyle C_{j}}$ระยะ เวลาใน การดำเนินการงาน${\displaystyle j}$.${\displaystyle C_{\max }}$คือเวลาแล้วเสร็จสูงสุด หรือที่เรียกว่าmakespanบางครั้งเราอาจสนใจ เวลาแล้วเสร็จ เฉลี่ย (ค่าเฉลี่ยของ${\displaystyle C_{j}}$ตลอดj ทั้งหมด ) ซึ่งบางครั้งเรียกว่า mft (เวลาสิ้นสุดเฉลี่ย) ^{[ 4 ]}
• ${\displaystyle F_{j}}$เวลาดำเนินการของงานคือผลต่างระหว่างเวลาที่งานเสร็จสมบูรณ์และเวลาที่งานเริ่มดำเนินการ กล่าวคือ${\displaystyle F_{j}=C_{j}-r_{j}}$.
• ${\displaystyle L_{j}}$: การมาสายทุกงาน${\displaystyle j}$ได้รับกำหนดวันครบกำหนด${\displaystyle d_{j}}$การส่งงานล่าช้า${\displaystyle j}$ถูกกำหนดให้เป็น${\displaystyle C_{j}-d_{j}}$. บางครั้ง${\displaystyle L_{\max }}$ใช้เพื่อแสดงถึงความเป็นไปได้สำหรับปัญหาที่มีกำหนดเวลา ที่จริงแล้ว การใช้การค้นหาแบบไบนารีความซับซ้อนของเวอร์ชันความเป็นไปได้จะเทียบเท่ากับการลดค่าต่ำสุดของ${\displaystyle L_{\max }}$.
• ${\displaystyle U_{j}}$: อัตราผลผลิตทุกงานจะมีกำหนดส่ง${\displaystyle d_{j}}$งานที่เสร็จตรงเวลาจะได้รับกำไรต่อหน่วย กล่าวคือ${\displaystyle U_{j}=1}$ถ้า${\displaystyle C_{j}\leq d_{j}}$และ ${\displaystyle U_{j}=0}$มิฉะนั้น บางครั้งความหมายของ${\displaystyle U_{j}}$ในเอกสารทางวิชาการมีการกลับด้าน ซึ่งถือว่าเทียบเท่ากันเมื่อพิจารณาปัญหาในแง่ของการตัดสินใจ แต่จะสร้างความแตกต่างอย่างมากสำหรับการประมาณค่า
• ${\displaystyle T_{j}}$การมาสายในทุกงาน${\displaystyle j}$ได้รับกำหนดวันครบกำหนด${\displaystyle d_{j}}$ความล่าช้าในการทำงาน${\displaystyle j}$ถูกกำหนดให้เป็น${\displaystyle T_{j}=\max\{0,C_{j}-d_{j}\}}$.
• ${\displaystyle E_{j}}$: ความรวดเร็วทุกงาน${\displaystyle j}$ได้รับกำหนดวันครบกำหนด${\displaystyle d_{j}}$ความรวดเร็วของงาน${\displaystyle j}$ถูกกำหนดให้เป็น${\displaystyle E_{j}=\max\{0,d_{j}-C_{j}\}}$เป้าหมายนี้มีความสำคัญต่อการวางแผนการผลิตแบบทันเวลาพอดี (just-in-time scheduling)

นอกจากนี้ยังมีรูปแบบที่มีจุดประสงค์หลายประการแต่มีการศึกษาน้อยกว่ามาก^{[ 2 ]}

ต่อไปนี้เป็นตัวอย่างปัญหาบางประการที่กำหนดโดยใช้สัญลักษณ์ข้างต้น^{[ 1 ]}

• ${\displaystyle P_{2}\parallel C_{\max }}$– การกำหนดให้กับแต่ละ${\displaystyle n}$มอบหมายงานให้กับเครื่องจักรสองเครื่องที่เหมือนกันเครื่องใดเครื่องหนึ่ง เพื่อลดเวลาการประมวลผลรวมสูงสุดของเครื่องจักรทั้งสองเครื่องให้เหลือน้อยที่สุด นี่คือเวอร์ชันการเพิ่มประสิทธิภาพของปัญหาการแบ่งส่วน (Partition Problem)
• 1|prec|${\displaystyle L_{\max }}$- การมอบหมายกระบวนการที่มีข้อจำกัดด้านลำดับความสำคัญทั่วไปให้กับเครื่องเดียว เพื่อลดความล่าช้าสูงสุดให้น้อยที่สุด
• R|pmtn|${\displaystyle \sum C_{i}}$- การมอบหมายงานให้กับเครื่องคอมพิวเตอร์แบบขนานจำนวนหนึ่งที่ไม่เกี่ยวข้องกัน อนุญาตให้มีการขัดจังหวะ และลดเวลาในการทำงานให้แล้วเสร็จโดยรวมให้น้อยที่สุด
• J3|${\displaystyle p_{ij}=1}$|${\displaystyle C_{\max }}$– ปัญหาการผลิตชิ้นงานด้วยเครื่องจักร 3 เครื่อง โดยมีเวลาในการประมวลผลต่อหน่วย และเป้าหมายคือการลดเวลาแล้วเสร็จสูงสุดให้น้อยที่สุด
• ${\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }}$- การมอบหมายงานให้${\displaystyle m}$การจัดตารางงานแบบขนานโดยใช้เครื่องจักรที่เหมือนกัน โดยแต่ละงานจะมีเครื่องจักรจำนวนหนึ่งที่ต้องจัดตารางให้ทำงานพร้อมกัน เพื่อลดเวลาแล้วเสร็จสูงสุดให้น้อยที่สุด ดูการจัดตารางงานแบบขนาน (Parallel Task Scheduling )

• ตัวแปรทั้งหมดที่สำรวจข้างต้นเป็นแบบกำหนดได้เนื่องจากข้อมูลทั้งหมดเป็นที่รู้จักของผู้วางแผน นอกจากนี้ยังมี ตัวแปร แบบสุ่มซึ่งข้อมูลไม่เป็นที่รู้จักล่วงหน้า หรืออาจถูกรบกวนแบบสุ่ม^{[ 2 ]}
• ในเกมการกระจายภาระงาน แต่ละงานเป็นของตัวแทนเชิงกลยุทธ์ ซึ่งสามารถตัดสินใจได้ว่าจะจัดตารางงานไว้ที่ใดสมดุลแนชในเกมนี้อาจจะไม่ใช่สมดุลที่ดีที่สุด Aumann และ Dombb ^{[ 5 ]}ประเมินความไม่มีประสิทธิภาพของสมดุลในเกมการกระจายภาระงานหลายเกม

• การจัดตารางงานแบบเศษส่วน
• การกระจายภาระงาน (ด้านคอมพิวเตอร์) : การกระจายภาระงานอย่างเหมาะสมเป็นอีกคำหนึ่งที่ใช้เรียกการจัดตารางงานอย่างเหมาะสม

• Scheduling zoo (โดย Christoph Dürr, Sigrid Knust, Damien Prot, Óscar C. Vásquez): เครื่องมือออนไลน์สำหรับค้นหาปัญหาการจัดตารางเวลาที่เหมาะสมที่สุดโดยใช้สัญลักษณ์
• ผลลัพธ์ด้านความซับซ้อนสำหรับปัญหาการจัดตารางเวลา (โดย Peter Brucker, Sigrid Knust): การจำแนกประเภทของปัญหาการจัดตารางเวลาที่เหมาะสมที่สุดตามสิ่งที่ทราบเกี่ยวกับความซับซ้อนของเวลาในการดำเนินการ