ในคณิตศาสตร์ประยุกต์ปัญหาการจัดสรรทั่วไปสูงสุด (Maximum Generalized Assignment Problem ) เป็นปัญหาหนึ่งในการหาค่าเหมาะสมที่สุดเชิงการจัดเรียง (Combinatorial Optimization ) ปัญหานี้เป็นการขยายความของปัญหาการจัดสรร (Assignment Problem)ที่ทั้งงานและตัวแทน (Agent)มีขนาด นอกจากนี้ ขนาดของแต่ละงานอาจแตกต่างกันไปในแต่ละตัวแทน

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

ในกรณีพิเศษที่งบประมาณของตัวแทนทั้งหมดและต้นทุนของงานทั้งหมดเท่ากับ 1 ปัญหาจะลดลงเหลือเพียงปัญหาการจัดสรรงานเมื่อต้นทุนและกำไรของงานทั้งหมดไม่แตกต่างกันระหว่างตัวแทนต่างๆ ปัญหาจะลดลงเหลือเพียงปัญหาเป้สะพายหลังหลายใบ หากมีตัวแทนเพียงคนเดียว ปัญหาจะลดลงเหลือเพียงปัญหาเป้สะพายหลัง

ต่อไปนี้ เรามี สินค้า nชนิดและถัง เก็บ mชนิดแต่ละถังเก็บมีงบประมาณที่กำหนดไว้สำหรับถังเก็บ แต่ละถัง สินค้าแต่ละชิ้นจะมีกำไรและน้ำหนักที่กำหนดไว้วิธีแก้ปัญหาคือการจัดสรรสินค้าให้กับถังเก็บต่างๆ วิธีแก้ปัญหาที่เป็นไปได้คือวิธีแก้ปัญหาที่น้ำหนักรวมของสินค้าที่จัดสรรให้กับถังเก็บแต่ละถังมีค่าไม่เกิน กำไรของวิธีแก้ปัญหาคือผลรวมของกำไรจากการจัดสรรสินค้าแต่ละชนิดให้กับถังเก็บแต่ละถัง เป้าหมายคือการหาวิธีแก้ปัญหาที่เป็นไปได้ซึ่งให้กำไรสูงสุด ${\displaystyle a_{1}}$${\displaystyle a_{n}}$${\displaystyle b_{1}}$${\displaystyle b_{m}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$${\displaystyle b_{i}}$${\displaystyle a_{j}}$${\displaystyle p_{ij}}$${\displaystyle w_{ij}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$

ในทางคณิตศาสตร์ ปัญหาการมอบหมายงานทั่วไปสามารถกำหนดได้ในรูปของโปรแกรมจำนวนเต็ม :

${\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

ปัญหาการกำหนดทั่วไปเป็นปัญหาNP-hard [ ^{1 ] อย่างไรก็ตาม}มีการผ่อนคลายการเขียนโปรแกรมเชิงเส้นซึ่งให้การประมาณค่า^{[ 2 ]}${\displaystyle (1-1/e)}$

สำหรับรูปแบบปัญหาที่ไม่จำเป็นต้องกำหนดรายการทั้งหมดลงในถัง มีตระกูลของอัลกอริธึมสำหรับการแก้ปัญหา GAP โดยใช้การแปลเชิงคอมบินาทอริกของอัลกอริธึมใดๆ สำหรับปัญหากระเป๋าเป้สะพายหลังให้เป็นอัลกอริธึมประมาณค่าสำหรับ GAP ^{[ 3 ]}

การใช้อัลกอริธึมประมาณค่าใดๆ ALG สำหรับปัญหาเป้สะพายหลังสามารถสร้างการประมาณค่า ( ) สำหรับปัญหาการจัดสรรทั่วไปในลักษณะโลภโดยใช้แนวคิดกำไรส่วนเหลือได้ อัลกอริธึมสร้างตารางในรอบการทำซ้ำ โดยในแต่ละรอบการทำซ้ำ จะมี การเลือกรายการที่จะบรรจุลงในถังชั่วคราวการเลือกถังอาจเปลี่ยนแปลงได้ เนื่องจากอาจมีการเลือกรายการใหม่ในรอบการทำซ้ำถัดไปสำหรับถังอื่นๆ กำไรส่วนเหลือของรายการสำหรับถังคือถ้าไม่ได้เลือกสำหรับถังอื่น หรือ– ถ้าเลือกสำหรับถัง ${\displaystyle \alpha }$${\displaystyle \alpha +1}$${\displaystyle j}$${\displaystyle b_{j}}$${\displaystyle b_{j}}$${\displaystyle x_{i}}$${\displaystyle b_{j}}$${\displaystyle p_{ij}}$${\displaystyle x_{i}}$${\displaystyle p_{ij}}$${\displaystyle p_{ik}}$${\displaystyle x_{i}}$${\displaystyle b_{k}}$

ในเชิงทฤษฎี: เราใช้เวกเตอร์เพื่อระบุตารางเวลาเบื้องต้นในระหว่างการทำงานของอัลกอริธึม โดยเฉพาะอย่างยิ่งหมายความว่ารายการนั้นถูกกำหนดไว้ในช่องเก็บและหมายความว่ารายการนั้นไม่ได้ถูกกำหนดไว้ กำไรส่วนที่เหลือในการวนซ้ำจะแสดงด้วย โดยที่ถ้ารายการนั้นไม่ได้ถูกกำหนดไว้ (เช่น) และถ้ารายการนั้นถูกกำหนดไว้ในช่องเก็บ(เช่น) ${\displaystyle T}$${\displaystyle T[i]=j}$${\displaystyle x_{i}}$${\displaystyle b_{j}}$${\displaystyle T[i]=-1}$${\displaystyle x_{i}}$${\displaystyle j}$${\displaystyle P_{j}}$${\displaystyle P_{j}[i]=p_{ij}}$${\displaystyle x_{i}}$${\displaystyle T[i]=-1}$${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$${\displaystyle x_{i}}$${\displaystyle b_{k}}$${\displaystyle T[i]=k}$

อย่างเป็นทางการ:

ชุด${\displaystyle T[i]=-1{\text{ สำหรับ }}i=1\ldots n}$

สำหรับสิ่งที่ต้องทำ: ${\displaystyle j=1,\ldots ,m}$

เรียกใช้ ALG เพื่อหาคำตอบในการจัดกลุ่มโดยใช้ฟังก์ชันกำไรส่วนเหลือกำหนดให้รายการที่เลือกเป็น.${\displaystyle b_{j}}$${\displaystyle P_{j}}$${\displaystyle S_{j}}$

อัปเดตโดยใช้เช่นสำหรับทุก${\displaystyle T}$${\displaystyle S_{j}}$${\displaystyle T[i]=j}$${\displaystyle i\in S_{j}}$

• ปัญหาการมอบหมายงาน

• เคลเลอร์, ฮันส์; เพอร์ชี่, อุลริช; พิซิงเกอร์, เดวิด (19-03-2556) ปัญหากระเป๋าเป้สะพายหลัง สปริงเกอร์. ไอเอสบีเอ็น 978-3-540-24777-7.