การวิเคราะห์ข่ายงาน [ Network Analysis ]

การวิเคราะห์ข่ายงานเป็นเทคนิคการหาผลเฉลยที่เหมาะสมที่สุดของปัญหาที่สามารถเขียนในรูปของข่ายงานได้ ปัญหาเหล่านี้เช่น การผลิตสินค้า การกระจายสินค้า การจัดการทรัพยากร การติดตั้งอุปกรณ์อำนวยความสะดวก การวางแผนโครงการ หรือแม้แต่การวางแผนการเงิน เทคนิคที่จะนำมาศึกษามีอยู่ 4 แบบคือ
1. การหาระยะทางสั้นที่สุด ( Shortest Route Technique )
2. ต้นไม้แบบทอดข้ามที่เล็กที่สุด (Minimal Spanning Tree Technique)
3. การหาสายงานสูงสุด (Maximal Flow Technique)
4. การบริหารโครงงานด้วย ระเบียนวิธีวิถีวิกฤต (Critical Path Method :CPM)
และเทคนิคการประเมินค่าและควบคุมโครงงาน (Program Evaluation and Review Technique)

1. นิยาม
- ข่ายงาน (network) ประกอบด้วยเซ็ทของจุดและเส้นซึ่งเชื่อมระหว่างจุด เราเรียกจุดว่า บัพ(node) เขียนแทนด้วยวงกลมล้อมรอบต้วเลข
- เส้นที่เชื่อระหว่างบัพเรียกว่า เส้นเชื่อม (arc) เขียนแทนด้วยเส้นลูกศร
- การเรียกชื่อเส้นเชื่อมจะเรียกหมายเลขบัพที่อยู่ส่วนต้นและส่วนท้ายของเส้นเชื่อม
- เรียก บัพแรกว่า บัพเริ่มต้น (source node)
- เรียก บัพสุดท้ายว่า บัพปลายทาง (Sink node)
- สิ่งที่ไหลจากบัพหนึ่งไปอีกบัพหนึ่งเรียกว่า สายงาน (Flow)
- ถ้าสายงานไหลผ่านเส้นเชื่อมไปในทิศทางเดียวเรียกเส้นเชื่อมนั้นว่า เส้นเชื่อมแบบมีทิศทาง (directed arc)
- ถ้าสายงานไหลผ่านเส้นเชื่อมได้ทั้งไปและกลับเรียกเส้นเชื่อมนั้นว่า เส้นเชื่อมแบบไร้ทิศทาง (undirected arc)
- กิจกรรมเทียม (dummy activity) คือกิจกรรมที่ไม่ได้ปฏิบัติจริง เวลาและทรัพยากรของกิจกรรมเป็นศูนย์ แสดงกิจกรรมเทียมด้วยเส้นประ
- วิถี (path) เป็นลำดับของเส้นเชื่อมจากบัพเริ่มต้น ไปยัง บัพปลายทาง โดยบัพเริ่มต้นของแต่ละเส้นเชื่อมเป็นบัพสิ้นสุดของเส้นเชื่อมก่อนหน้านี้
- ลูกโซ่ (chain) คือวิถีที่เชื่อมบัพทุกบัพ โดยทุกเส้นเชื่อมไม่จำเป็นต้องมุ่งสู่บัพปลายทาง
- วัฏจักร (cycle) คือลูกโซ่ที่ทุกบัพเชื่อมต่อถึงกันหมด หรือเรียกว่า closed chain
- วงจร (circuit) คือวิถี ซึ่งบัพเริ่มต้นและบัพสุดท้ายเป็นบัพเดียวกัน หรือเรียกว่า closed path ทุกวงจรเป็นวัฏจักร แต่วัฏจักรไม่จำเป็นต้องเป็นวงจร
- ข่ายงานเชื่อมโยง (connected network) คือข่ายงานที่บัพทุกคู่ มีวิถีหรือโซ่อย่างน้อย 1 อันเชื่อมโยงอยู่
- ต้นไม้ (tree) คือข่ายงานเชื่อมโยงที่ไม่มีวัฏจักร
- ต้นไม้แบบทอดข้าม (spanning tree) คือ ข่ายงานเชื่อมโยงที่ประกอบด้วยบัพ n บัพ และเส้นเชื่อม n-1 เส้น และไม่มีวัฏจักรเกิดขึ้นในข่ายงานนี้
- ความจุของเส้นเชื่อม (arc capacity) คือปริมาณสายงานที่มากที่สุดที่เป็นไปได้บนเส้นเชื่อมนั้น source node จะมีปริมาณสายงานออกจากบัพมากกว่าปริมาณสายงานที่เข้าสู่บัพ sink node จะมีปริมาณสายงานเข้าสู่ node มากกว่าปริมาณสายงานออกจาก node ส่วน node ระหว่างกลาง (intermediate node) มีปริมาณสายงานเข้าเท่ากับปริมาณสายงานออกจาก node

2. การหาระยะทางสั้นที่สุด (Shortest-Route)
เป็นการหาวิถีจาก node เริ่มต้นไปยัง node ปลายทาง เป็นวิถีที่มีระยะทางที่สั้นที่สุดซึ่งไม่จำเป็นต้องผ่านทุก node
มีขั้นตอนดังนี้
1. เริ่มจากnodeเริ่มต้น เลือกnodeที่เชื่อมกับnodeเริ่มต้นและมีระยะทางสั้นที่สุด สมมุติให้เป็น node j node ที่ถูกเลือกเรียกว่า Solved node ส่วนnodeที่ยังไม่ถูกเลือกเรียกว่า Unsolved node รวมระยะทางไว้ที่nodeล่าสุด
2. จาก node ที่ถูกเลือกแล้ว (solved node) ที่มีอยู่ พิจารณาnode ที่ยังไม่ถูกเลือก (Unsolved node) ทุกnodeที่เชื่อมกับ nodeที่ถูกเลือกไว้แล้ว เลือกnodeที่เชื่อมต่อแล้วมีระยะทางจาก nodeเริ่มต้นถึงnode นั้นน้อยที่สุดเชื่อมแล้วรวมระยะทางไว้ที่nodeล่าสุด
3. ตรวจดูว่าวิถีที่มีอยู่ถึง nodeปลายทางหรือยัง ถ้าถึงnodeปลายทางแล้วให้รวมระยะทางทั้งหมด ถ้ายังไม่ถึงnodeปลายทาง ก็ทำซ้ำตั้งแต่ขั้นที่สอง

3. การหาต้นไม้แบบทอดข้ามที่เล็กที่สุด (Minimal Spanning Tree)
spanning tree คือ ข่ายงานเชื่อมโยงที่มี n node และมีเส้นเชื่อม n-1 เส้น spanning tree จึงมีได้หลายแบบ แต่แบบที่มีระยะทางรวมสั้นที่สุดคือต้นไม้แบทอดข้ามที่เล็กที่สุด (minimal spanning tree) มีขั้นตอนการหาดังนี้
1. เลือก node ใดๆ 1 node แล้วเชื่อมnodeกับnodeอื่นที่มีระยะทางในการเชื่อมสั้นที่สุด
2. จากnodeที่เชื่อมแล้วทั้งหมด พิจารณาว่าสามารถเชื่อมกับ nodeที่ยังไม่ถูกเชื่อมได้กี่ode เลือกnodeที่ยังไม่ถูกเชื่อมที่ระยะทางห่างจากnodeที่เชื่อมแล้วน้อยที่สุด ถ้ามีมากกว่า 1node ก็เลือก nodeใดๆก็ได้
3. ตรวจสอบว่าทุกnodeถูกเชื่อมหมดหรือยัง ถ้าเชื่อมหมดแล้วรวมระยะทางทั้งหมด ถ้ายังเชื่อมไม่หมดให้ย้อนกลับไปทำขั้นที่ 2 อีก

4.การหาสายงานสูงสุด (Maximal Flow)
เป็นการหาปริมาณสายงานจากnodeเริ่มต้นไปยังnodeปลายทางให้มากที่สุดเท่าที่ความจุของแต่ละเส้นเชื่อมจะมีให้ได้ หลักการคือส่งสายงานจากnodeเริ่มต้นไปให้มากที่สุดจนถึง nodeปลายทางแล้วพิจารณาความจุ (capacity) ของเส้นเชื่อมว่ายังมีสายงานเหลืออยู่(residual) ให้ส่งสายงานไปจนถึงnodeปลายทางได้หรือไม่ ทำการตกแต่ง (argment) วิถีที่มีอยู่ จนกว่าจะเพิ่มสายงานอีกไม่ได้
ขั้นตอนดังนี้
1.พิจารณาวิถีจากnodeเริ่มต้นไปยังnodeปลายทางทุกวิถีที่เป็นไปได้ เลือกวิถีที่ส่งสายงานได้มากที่สุด คือมีความจุของเส้นเชื่อมที่น้อยที่สุดในวิถีนั้นมากกว่าวิถีอื่นๆ
2.ปรับความจุที่เหลือในแต่ละเส้นเชื่อมของวิถีที่ส่งสายงานไปล่าสุด
3.ตรวจสอบดูว่ายังมีวิถีใดบ้างที่มีสายงานตกค้างอยู่ ที่สามารถส่งสายงานไปจนถึงnodeปลายทางได้ ถ้าไม่มีวิถีที่ส่งสายงานไปจนถึงnodeปลายทางได้อีก แสดงว่าได้สายงานสูงสุดแล้ว รวมปริมาณสายงานทั้งหมดที่ส่งไป แต่ถ้ายังมีวิถีทที่ส่งสายงานไปจนถึงnodeปลายทางได้อีก ให้กลับไปทำข้อ 1 ใหม่

5. การบริหารโครงงานด้วยระเบียบวิธีวิถีวิฤต และเทคนิคการควบคุมโครงการ(CPM และ PERT)
คือการควบคุมให้งานเสร็จภายในเวลาที่กำหนด
5.1 แผนภูมิแกนท์ (Grant Chart)
-เหมาะกับโครงงานที่มีกิจกรรมไม่ซับซ้อนนัก
-แสดงความสัมพันธ์ชองกิจกรรมกับเวลา

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

5.2 ระเบียบวิธีวิถีวิกฤต ( Critical Path Method :CPM)
ระเบียบวิธีวิถีวิฤต เป็นตัวแบบข่ายงานชนิดตัวแบบเชิงกำหนด (deterministic model) กล่าวคือ เวลาของกิจกรรมต่างๆในโครงงานและค่าใช้จ่ายของแต่ละกิจกรรม ทราบค่าแน่นอน วิธีนี้จึงมักใช้กับโครงงานประเภทที่เคยมีผู้ทำมาก่อน หรือหน่วยงานมีความคุ้นเคยกบกิจกรรมต่างๆในโครงงานทำให้สามารถประมาณเวลาของกิจกรรม และค่าใช้จ่ายได้แม่นยำ

วิถีวิกฤต (critical path) คือเส้นทางที่ประกอบด้วยกิจกรรมของข่ายงานตั้งแต่nodeเริ่มต้นจนถึงnodeปลายทาง โดยที่แต่ละกิจกรรมบนเส้นทางนี้ไม่สามารถยืดหยุ่นเวลาของกิจกรรมได้เลย ดังนั้นหากกิจกรรมใดบนวิถีวิกฤตล่าช้าจะส่งผลให้โครงงานทั้งโครงงานล่าช้า

การหาวิถีวิกฤต มีขั้นตอนดังนี้
1. คำนวณเวลาเริ่มต้นที่เร็วที่สุด (Earliest start time : ES) คือเวลาที่กิจกรรมบนข่ายงานเริ่มต้นได้เร็วที่สุด โดยไม่กระทบต่อกิจกรรมก่อนหน้านี้
2. คำนวณเวลาเสร็จเร็วที่สุด (Earliest finish time : EF) คือเวลาที่กิจกรรมจะเสร็จได้เร็วที่สุด
3. คำวนวณเวลาเริ่มต้นที่ช้าที่สุด (Latest start time : LS) คือเวลาที่กิจกรรมจะเริ่มต้นได้ อย่างช้าที่สุดโดยไม่ทำให้โครงงานทั้งโครงงานล่าช้า
4. คำนวณเวลาเสร็จที่ช้าที่สุด (Latest finish time : LF) คือเวลาที่กิจกรรมจะเสร็จได้อย่างช้าที่สุด โดยไม่ทำให้โครงงานทั้งโครงงานล่าช้า
5. คำนวณเวลาที่เหลือ (slack time) ของแต่ละกิจกรรม จากผลต่างของเวลาเริ่มต้นช้าที่สุด (LS) กับเวลาเริ่มต้นเร็วที่สุด(ES) หรือคำนวณจากผลต่างของเวลาเสร็จช้าที่สุด (LF) กับเวลาเสร็จเร็วที่สุด (EF)
slack = LS-ES = LF - EF

6. พิจารณากิจกรรมที่ไม่มีเวลาเหลือ คือ slack=0 เป็นกิจกรรมวิฤต
7. พิจารณาเส้นทางที่ประกอบด้วยกิจกรรมวิกฤต เป็นวิถีวิกฤต

การคำนวณหา ES , EF
กิจกรรมแรกของโครงงานจะมีเวลาเริ่มต้นเป็น 0 เพราะไม่ต้องรอกิจกรรมอื่น จึงเริ่มต้นได้เลย
เวลาเสร็จเร็วที่สุดของกิจกรรมแรกคือ ผลบอกของเวลาเริ่มต้นที่เร็วที่สุด กับเวลาของกิจกรรมนั้น (dij) = EF = ES + dij
สำหรับกิจกรรมอื่นๆเวลาเริ่มต้นที่เร็วที่สุด คือ ค่าที่สูงสุด ของเวลาเสร็จเร็วที่สุดของกิจกรรมทั้งหมดก่อนหน้าที่เข้าสู่ node ของกิจกรรมนี้
ESjk = Max(EFij)

การคำนวณ ES , EF จากกิจกรรมแรกถึงกิจกรรมสุดท้ายเรียกว่าการคำนวณไปข้างหน้า (forward pass)

การคำนวณหา LS , LF
จะทำการคำนวณหลังจากการคำนวณ ES , EF ตลอดโครงงานแล้ว โดยเริ่มต้นจากกิจกรรมสุดท้ายย้อยไปจนถึงกิจกรรมแรกเรียกว่าการคำนวณย้อนหลัง (backward pass)

ขั้นแรกที่กิจกรรมสุดท้าย ให้ เวลาเสร็จช้าที่สุด (LF) เท่ากับ เวลาเสร็จเร็วที่ด (EF) และ เวลาเริ่มต้นช้าที่สุด LS คือผลต่างของ เวลาเสร็จช้าที่สุด (LF) กับเวลาของกิจกรรมนั้น (dij) จะได้
LS = LF - dij

ขั้นต่อไปที่กิจกรรมอื่นๆ เวลาเสร็จที่ช้าที่สุดของกิจกรรมที่เข้าสู่ node คือ ค่าที่ที่สุด ของเวลาเริ่มต้นช้าที่สุดของทุกกิจกรรมที่ออกจากnode นี้

5.3 เพิร์ต (PERT : Program Evaluation and Review Technique)