فهرست مقاله
وقتی خدمت‌دهنده مشغول است، رد تماس و نگه‌داشتن آن در صف دو تصمیم متفاوت‌اند. صف هم نامحدود نیست و بعضی منتظران پیش از شروع خدمت منصرف می‌شوند. این درس یک شبیه‌سازی محدود با یک خدمت‌دهنده، دو جای انتظار و زمان‌های کاملاً ساختگی می‌سازد. هدف، بررسی ترتیب تصمیم‌هاست؛ تماس، کارشناس واقعی، ظرفیت مرکز تماس و توافق سطح خدمت اندازه‌گیری نمی‌شوند.
۱. پذیرش، انتظار و خدمت را جدا نگه داریم
هر ورودی شناسه، زمان ورود، مدت خدمت و مدت تحمل انتظار دارد. مدت خدمت از قبل داده شده است و با نیاز واقعی تماس‌گیرنده تخمین زده نمی‌شود. همهٔ زمان‌ها عدد صحیحِ میلی‌ثانیه‌اند؛ عددهای نمونه عمداً کوچک‌اند تا پاسخ دستی خوانا باشد و مدت معقولِ تماس واقعی معرفی نمی‌شوند.
یک تماس می‌تواند بی‌انتظار وارد خدمت شود، مدتی در صف بماند، هنگام انتظار منصرف شود یا به علت پر بودن صف رد شود. ظرفیت دو فقط منتظران را می‌شمارد؛ تماسِ در خدمت جزو این دو نیست. پس در لحظه‌ای با صف پُر، سه تماس می‌توانند داخل مدل باشند: یکی در خدمت و دو منتظر.
در مدل ظرفیت تماس هم‌زمان، درخواستِ بدون جایگاه رد می‌شد و انتظار نداشت. اینجا مدت خدمت از لحظهٔ شروع واقعیِ مدل حساب می‌شود؛ منتظر، پایانِ از پیش تعیین‌شدهٔ بیرونی برای اشغال خط ندارد. ورود به صف نیز تضمین شروع خدمت نیست، چون مهلت انتظار می‌تواند زودتر برسد.
۲. قدیمی‌ترین انتظار معتبر را برای خدمت برداریم
قاعدهٔ FCFS در این مثال یعنی از میان منتظرانِ باقی‌مانده، کسی زودتر خدمت بگیرد که زودتر وارد شده است. ورودهای هم‌زمان به ترتیب ردیف ورودی‌اند، نه ترتیب واژگانی شناسه. بنابراین تولیدکنندهٔ داده باید همین ترتیب را حفظ کند؛ برنامه زمان‌های نامرتب را برای پنهان‌کردن اشکال ورودی خودکار مرتب نمی‌کند.
خدمت قطع نمی‌شود. وقتی پایانِ خدمت رخ می‌دهد، خدمت‌دهنده آزاد و بلافاصله قدیمی‌ترین منتظر وارد می‌شود. ورود تازهٔ همان لحظه نمی‌تواند از او جلو بزند. اگر کسی در صف نباشد، ورود تازه خدمت را آغاز می‌کند. کسی که به دلیل صف پُر رد شده، جای آینده رزرو نمی‌کند و خودکار دوباره تماس نمی‌گیرد.
heapq پایتون زمان کوچک‌تر را زودتر برمی‌گرداند، اما به‌تنهایی سیاست صف تماس نیست. صف رویداد را از صف منتظران جدا نگه می‌داریم: اولی زمان اجرای پایان یا انصراف را تعیین می‌کند؛ دومی ترتیب افراد منتظر را. مخلوط‌کردن این دو می‌تواند تماسِ دارای مهلت کوتاه را بی‌دلیل جلو بیندازد.
۳. مهلت انصراف را با پایان خدمت اشتباه نگیریم
مهلت هر منتظر برابر زمان ورود به‌علاوهٔ تحمل انتظار است. سیاست مرزی خودمان صریح است: ابتدا پایان خدمت و واگذاری به منتظر قدیمی، سپس انقضای انتظارِ باقی‌مانده و در آخر ورودهای تازه پردازش می‌شوند. اگر آزادشدن خدمت و مهلت یک منتظر دقیقاً برابر باشند، در این مدل شروع خدمت برنده است.
پس از شروع خدمت، مهلت انتظار دیگر آن را قطع نمی‌کند. تحمل صفر نیز دو حالت دارد: اگر خدمت‌دهنده آزاد باشد، تماس فوری شروع می‌شود؛ اگر مشغول باشد، تماس همان لحظه منصرف می‌شود. این انصرافِ بی‌انتظار را با ردِ صف پُر یکی نمی‌کنیم؛ در قرارداد ما بررسی تحمل صفر پیش از پر بودن صف انجام می‌شود.
راهنمای زمان‌بندی SimPy توضیح می‌دهد که رویدادهای هم‌زمان در رایانه ترتیبی اجرا می‌شوند و قاعدهٔ تساوی اهمیت دارد. ما SimPy را اجرا نکرده‌ایم؛ اولویت‌های پایان، انقضا و ورود سیاست تألیفی همین کدند. وضوحِ ترتیب به معنی تضمین عدالت برای هر کاربرد یا دقت زمانیِ مرکز تلفن واقعی نیست.
۴. رد مرحله‌ای و کد را با مرجع دستی مقایسه کنیم
فایل call_queue.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. حداکثر شانزده ورودی با شناسهٔ یکتا داریم. ورود از صفر تا ۶۰۰۰۰، خدمت از یک تا ۱۰۰۰ و تحمل از صفر تا ۱۰۰۰ میلی‌ثانیه است؛ bool جای عدد پذیرفته نیست. ظرفیت انتظار از صفر تا چهار می‌تواند تغییر کند.
"""Original finite one-server FCFS waiting/abandonment simulation; no calls or clock."""
from collections import deque
from itertools import combinations_with_replacement, count, product
import copy
import heapq
import json
import platform
import re
def validate(calls, waiting_capacity):
if type(waiting_capacity) is not int or not 0 <= waiting_capacity <= 4:
raise ValueError('waiting capacity must be actual integer 0..4')
if type(calls) is not list or len(calls) > 16:
raise ValueError('at most sixteen supplied calls')
seen = set();previous = 0
for call in calls:
if type(call) is not dict or set(call) != {'id', 'arrival_ms', 'service_ms', 'patience_ms'}:
raise ValueError('exact call fields required')
cid = call['id']
if type(cid) is not str or not re.fullmatch(r'[A-Za-z][A-Za-z0-9_]{0,7}', cid) or cid in seen:
raise ValueError('unique bounded ASCII identifier required')
for field, low, high in [('arrival_ms', previous, 60000), ('service_ms', 1, 1000), ('patience_ms', 0, 1000)]:
if type(call[field]) is not int or not low <= call[field] <= high:
raise ValueError('integer time/order outside contract')
seen.add(cid);previous = call['arrival_ms']
def simulate(calls, waiting_capacity=2):
validate(calls, waiting_capacity)
records = {call['id']: {**call, 'state': 'pending', 'started_ms': None,
'finished_ms': None, 'abandoned_ms': None, 'waiting_ms': None}
for call in calls}
events = [];serial = count();waiting = deque();active = None;peak = 0;trace = []
for call in calls:
heapq.heappush(events, (call['arrival_ms'], 2, next(serial), 'arrival', call['id']))
def log(t, cid, kind):
trace.append({'at_ms': t, 'id': cid, 'event': kind})
def start(cid, t):
nonlocal active
row = records[cid]
row.update(state='in_service', started_ms=t, waiting_ms=t - row['arrival_ms'])
active = cid;log(t, cid, 'service_started')
heapq.heappush(events, (t + row['service_ms'], 0, next(serial), 'complete', cid))
while events:
t, _, _, kind, cid = heapq.heappop(events);row = records[cid]
if kind == 'complete':
assert cid == active and row['state'] == 'in_service'
row.update(state='completed', finished_ms=t);log(t, cid, 'completed');active = None
# Service grant to the oldest waiting caller precedes equal-time expiry.
if waiting:
start(waiting.popleft(), t)
elif kind == 'expire':
if row['state'] == 'waiting':
waiting.remove(cid)
row.update(state='abandoned', abandoned_ms=t, waiting_ms=t - row['arrival_ms'])
log(t, cid, 'abandoned')
else:
log(t, cid, 'arrived')
if active is None:
start(cid, t)
elif row['patience_ms'] == 0:
row.update(state='abandoned', abandoned_ms=t, waiting_ms=0);log(t, cid, 'abandoned')
elif len(waiting) >= waiting_capacity:
row['state'] = 'rejected_full';log(t, cid, 'rejected_full')
else:
row['state'] = 'waiting';waiting.append(cid);peak = max(peak, len(waiting));log(t, cid, 'queued')
heapq.heappush(events, (t + row['patience_ms'], 1, next(serial), 'expire', cid))
assert active is None and not waiting
return {'calls': [records[call['id']] for call in calls], 'trace': trace,
'peak_waiting': peak, 'terminal_counts': {state: sum(row['state'] == state for row in records.values())
for state in ['completed', 'abandoned', 'rejected_full']}}
def call(cid, arrival, service, patience):
return {'id': cid, 'arrival_ms': arrival, 'service_ms': service, 'patience_ms': patience}
def reference_ticks(calls, capacity):
"""Independent tiny-fixture reference: visit every millisecond, no event heap."""
result = {x['id']: ['pending', None, None, None, None] for x in calls}
original = {x['id']: x for x in calls};queue = [];serving = None;end = None
final_time = max((x['arrival_ms'] for x in calls), default=0) + sum(x['service_ms'] for x in calls) + max((x['patience_ms'] for x in calls), default=0) + 1
for t in range(final_time + 1):
if serving is not None and end == t:
result[serving][0] = 'completed';result[serving][2] = t;serving = None;end = None
if queue:
serving = queue.pop(0);row = original[serving]
result[serving][0:2] = ['in_service', t];result[serving][4] = t - row['arrival_ms'];end = t + row['service_ms']
for cid in queue.copy():
row = original[cid]
if row['arrival_ms'] + row['patience_ms'] == t:
result[cid] = ['abandoned', None, None, t, row['patience_ms']];queue.remove(cid)
for row in calls:
if row['arrival_ms'] != t:
continue
cid = row['id']
if serving is None:
serving = cid;end = t + row['service_ms'];result[cid] = ['in_service', t, None, None, 0]
elif row['patience_ms'] == 0:
result[cid] = ['abandoned', None, None, t, 0]
elif len(queue) >= capacity:
result[cid] = ['rejected_full', None, None, None, None]
else:
queue.append(cid);result[cid][0] = 'waiting'
return result
def compact(answer):
return {x['id']: [x['state'], x['started_ms'], x['finished_ms'], x['abandoned_ms'], x['waiting_ms']]
for x in answer['calls']}
def rejects(fn):
try:
fn()
except ValueError:
return True
return False
def run_example():
fixture = [call('A', 0, 10, 0), call('B', 1, 6, 9), call('C', 2, 4, 3),
call('D', 6, 3, 20), call('E', 10, 2, 0), call('F', 10, 2, 10), call('G', 10, 1, 20)]
before = copy.deepcopy(fixture);answer = simulate(fixture)
hand = {'A': ['completed', 0, 10, None, 0], 'B': ['completed', 10, 16, None, 9],
'C': ['abandoned', None, None, 5, 3], 'D': ['completed', 16, 19, None, 10],
'E': ['abandoned', None, None, 10, 0], 'F': ['completed', 19, 21, None, 9],
'G': ['rejected_full', None, None, None, None]}
fifo = simulate([call('Z', 0, 2, 0), call('B', 0, 1, 10), call('A', 0, 1, 10)])
no_jump = simulate([call('A', 0, 2, 0), call('B', 1, 1, 10), call('C', 2, 1, 10)], 1)
oracle = []
for arrivals in combinations_with_replacement([0, 1, 2], 2):
for service in product([1, 2], repeat=2):
for patience in product([0, 1, 2], repeat=2):
rows = [call('X', arrivals[0], service[0], patience[0]), call('Y', arrivals[1], service[1], patience[1])]
for capacity in [0, 1, 2]:
oracle.append(compact(simulate(rows, capacity)) == reference_ticks(rows, capacity))
completed = sorted((x for x in answer['calls'] if x['state'] == 'completed'), key=lambda x: x['started_ms'])
checks = {
'literal_seven_caller_hand_timeline': compact(answer) == hand,
'terminal_partition_and_peak_waiting': answer['terminal_counts'] == {'completed': 4, 'abandoned': 2, 'rejected_full': 1} and answer['peak_waiting'] == 2,
'equal_completion_grant_precedes_waiting_expiry': hand['B'] == compact(answer)['B'] and compact(answer)['B'][1] == fixture[1]['arrival_ms'] + fixture[1]['patience_ms'],
'waiting_deadline_abandons_before_service': compact(answer)['C'] == ['abandoned', None, None, 5, 3],
'waiting_expiry_does_not_interrupt_started_service': compact(answer)['F'] == ['completed', 19, 21, None, 9],
'equal_arrivals_keep_input_order_not_lexical_id': [x['id'] for x in fifo['trace'] if x['event'] == 'service_started'] == ['Z', 'B', 'A'],
'existing_waiter_precedes_new_equal_time_arrival': compact(no_jump)['B'][1] == 2 and compact(no_jump)['C'][1] == 3,
'zero_wait_capacity_still_allows_idle_server': simulate([call('A', 0, 2, 0), call('B', 1, 1, 4)], 0)['terminal_counts'] == {'completed': 1, 'abandoned': 0, 'rejected_full': 1},
'zero_patience_can_start_idle_but_not_wait_busy': compact(simulate([call('A', 0, 2, 0), call('B', 1, 1, 0)])) == {'A': ['completed', 0, 2, None, 0], 'B': ['abandoned', None, None, 1, 0]},
'full_queue_rejection_does_not_reserve_future_service': compact(answer)['G'] == ['rejected_full', None, None, None, None] and completed[-1]['finished_ms'] == 21,
'single_server_intervals_do_not_overlap': all(a['finished_ms'] <= b['started_ms'] for a, b in zip(completed, completed[1:])),
'empty_input_is_a_valid_finite_simulation': simulate([]) == {'calls': [], 'trace': [], 'peak_waiting': 0, 'terminal_counts': {'completed': 0, 'abandoned': 0, 'rejected_full': 0}},
'parameter_and_time_types_bounds': all(rejects(fn) for fn in [lambda: simulate([], True), lambda: simulate([], 5), lambda: simulate([call('A', 0, 0, 1)]), lambda: simulate([call('A', 0, 1, -1)]), lambda: simulate([call('A', True, 1, 1)]), lambda: simulate([call('A', 0, 1001, 1)]), lambda: simulate([call('A', 60001, 1, 1)])]),
'input_fields_order_identity_and_count': all(rejects(lambda x=x: simulate(x)) for x in [[call('A', 1, 1, 1), call('B', 0, 1, 1)], [call('A', 0, 1, 1)] * 2, [call('A', 0, 1, 1)] * 17, [{'id': 'A'}], (call('A', 0, 1, 1),)]),
'independent_millisecond_reference': all(oracle) and compact(answer) == reference_ticks(fixture, 2),
'input_is_preserved_and_rerun_deterministic': fixture == before and simulate(fixture) == answer,
}
assert all(type(x) is bool and x for x in checks.values()), checks
return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
'example_kind': 'Original finite synthetic one-server FCFS queue; no measured service/call-center/SLA result',
'policy': 'completion plus grant to oldest waiting caller, then waiting expiry, then stable-input-order arrivals; patience applies only before service',
'hand_compact': hand, 'simulation': answer,
'independent_two_caller_scenarios_inside_one_group': len(oracle), 'checks': checks}
if __name__ == '__main__':
print(json.dumps(run_example(), ensure_ascii=False, indent=2))
در جدول دستی، A از صفر تا ده خدمت می‌گیرد. B در یک می‌آید و نه میلی‌ثانیه تحمل دارد؛ دقیقاً در ده، پیش از انقضا وارد خدمت و در شانزده تمام می‌شود. C در دو می‌آید و با تحمل سه، در پنج منصرف می‌شود؛ پس جای انتظارش پیش از ورود شش آزاد شده است.
D در شش وارد و از شانزده تا نوزده خدمت می‌گیرد. سه ورودیِ زمان ده به ترتیب E,F,G هستند. اولی تحمل صفر دارد و منصرف می‌شود؛ دومی پشت D می‌ماند و سومی صف را پُر می‌بیند و رد می‌شود. F از نوزده تا بیست‌ویک خدمت دارد؛ مهلت بیست، خدمتِ شروع‌شده را قطع نمی‌کند.
خروجی چهار خدمت کامل، دو انصراف و یک ردِ صف پُر است؛ قلهٔ انتظار دو نفر است. شانزده گروه بررسی اجرا شده‌اند. مرجع مستقل به‌جای heap، تک‌تک میلی‌ثانیه‌ها و فهرست انتظار را می‌پیماید. ۶۴۸ سناریوی کوچکِ دونفره در یک گروه با آن مقایسه می‌شوند؛ جدول هفت‌ورودیِ دستی هم جداست و تکرار اجرا بررسی تازه محسوب نمی‌شود.
۵. نتیجهٔ ساختگی را SLA واقعی معرفی نکنیم
زمان انتظارِ خدمت‌گرفته‌ها به‌ترتیب صفر، نه، ده و نه میلی‌ثانیه است. برای ردِ صف پُر، waiting_ms تهی می‌ماند، چون تماس وارد صف نشده؛ انصراف فوری انتظار صفر دارد. این تفاوت جلوی یکی‌شمردنِ حالت‌های متفاوت را می‌گیرد. هیچ‌کدام میانگین بلندمدت، احتمال انصراف مشتری یا پیش‌بینی نیاز به نیروی انسانی نیستند.
{
"python": "3.14.5",
"dependencies": "Python standard library only",
"example_kind": "Original finite synthetic one-server FCFS queue; no measured service/call-center/SLA result",
"policy": "completion plus grant to oldest waiting caller, then waiting expiry, then stable-input-order arrivals; patience applies only before service",
"hand_compact": {
"A": [
"completed",
0,
10,
null,
0
],
"B": [
"completed",
10,
16,
null,
9
],
"C": [
"abandoned",
null,
null,
5,
3
],
"D": [
"completed",
16,
19,
null,
10
],
"E": [
"abandoned",
null,
null,
10,
0
],
"F": [
"completed",
19,
21,
null,
9
],
"G": [
"rejected_full",
null,
null,
null,
null
]
},
"simulation": {
"calls": [
{
"id": "A",
"arrival_ms": 0,
"service_ms": 10,
"patience_ms": 0,
"state": "completed",
"started_ms": 0,
"finished_ms": 10,
"abandoned_ms": null,
"waiting_ms": 0
},
{
"id": "B",
"arrival_ms": 1,
"service_ms": 6,
"patience_ms": 9,
"state": "completed",
"started_ms": 10,
"finished_ms": 16,
"abandoned_ms": null,
"waiting_ms": 9
},
{
"id": "C",
"arrival_ms": 2,
"service_ms": 4,
"patience_ms": 3,
"state": "abandoned",
"started_ms": null,
"finished_ms": null,
"abandoned_ms": 5,
"waiting_ms": 3
},
{
"id": "D",
"arrival_ms": 6,
"service_ms": 3,
"patience_ms": 20,
"state": "completed",
"started_ms": 16,
"finished_ms": 19,
"abandoned_ms": null,
"waiting_ms": 10
},
{
"id": "E",
"arrival_ms": 10,
"service_ms": 2,
"patience_ms": 0,
"state": "abandoned",
"started_ms": null,
"finished_ms": null,
"abandoned_ms": 10,
"waiting_ms": 0
},
{
"id": "F",
"arrival_ms": 10,
"service_ms": 2,
"patience_ms": 10,
"state": "completed",
"started_ms": 19,
"finished_ms": 21,
"abandoned_ms": null,
"waiting_ms": 9
},
{
"id": "G",
"arrival_ms": 10,
"service_ms": 1,
"patience_ms": 20,
"state": "rejected_full",
"started_ms": null,
"finished_ms": null,
"abandoned_ms": null,
"waiting_ms": null
}
],
"trace": [
{
"at_ms": 0,
"id": "A",
"event": "arrived"
},
{
"at_ms": 0,
"id": "A",
"event": "service_started"
},
{
"at_ms": 1,
"id": "B",
"event": "arrived"
},
{
"at_ms": 1,
"id": "B",
"event": "queued"
},
{
"at_ms": 2,
"id": "C",
"event": "arrived"
},
{
"at_ms": 2,
"id": "C",
"event": "queued"
},
{
"at_ms": 5,
"id": "C",
"event": "abandoned"
},
{
"at_ms": 6,
"id": "D",
"event": "arrived"
},
{
"at_ms": 6,
"id": "D",
"event": "queued"
},
{
"at_ms": 10,
"id": "A",
"event": "completed"
},
{
"at_ms": 10,
"id": "B",
"event": "service_started"
},
{
"at_ms": 10,
"id": "E",
"event": "arrived"
},
{
"at_ms": 10,
"id": "E",
"event": "abandoned"
},
{
"at_ms": 10,
"id": "F",
"event": "arrived"
},
{
"at_ms": 10,
"id": "F",
"event": "queued"
},
{
"at_ms": 10,
"id": "G",
"event": "arrived"
},
{
"at_ms": 10,
"id": "G",
"event": "rejected_full"
},
{
"at_ms": 16,
"id": "B",
"event": "completed"
},
{
"at_ms": 16,
"id": "D",
"event": "service_started"
},
{
"at_ms": 19,
"id": "D",
"event": "completed"
},
{
"at_ms": 19,
"id": "F",
"event": "service_started"
},
{
"at_ms": 21,
"id": "F",
"event": "completed"
}
],
"peak_waiting": 2,
"terminal_counts": {
"completed": 4,
"abandoned": 2,
"rejected_full": 1
}
},
"independent_two_caller_scenarios_inside_one_group": 648,
"checks": {
"literal_seven_caller_hand_timeline": true,
"terminal_partition_and_peak_waiting": true,
"equal_completion_grant_precedes_waiting_expiry": true,
"waiting_deadline_abandons_before_service": true,
"waiting_expiry_does_not_interrupt_started_service": true,
"equal_arrivals_keep_input_order_not_lexical_id": true,
"existing_waiter_precedes_new_equal_time_arrival": true,
"zero_wait_capacity_still_allows_idle_server": true,
"zero_patience_can_start_idle_but_not_wait_busy": true,
"full_queue_rejection_does_not_reserve_future_service": true,
"single_server_intervals_do_not_overlap": true,
"empty_input_is_a_valid_finite_simulation": true,
"parameter_and_time_types_bounds": true,
"input_fields_order_identity_and_count": true,
"independent_millisecond_reference": true,
"input_is_preserved_and_rerun_deterministic": true
}
}در سطل توکن برای درخواست ابزار، بودجهٔ پذیرش مسئلهٔ جدا بود و درخواستِ ردشده در صف نمی‌ماند. این شبیه‌سازی هم به سرویس واقعی وصل نیست، توزیع ورود نمی‌سازد و قانون لیتل یا فرمول ارلانگ را برای ظرفیت‌گذاری به کار نمی‌برد. منابع در ۲۵ مهر ۱۴۰۵ خوانده شدند؛ نسخهٔ مستندات از اجرای واقعی جدا ثبت شده است.
پرسش اول: چرا B در مهلت دقیق ده منصرف نشد؟ پاسخ: پایان و واگذاری خدمت اولویت بالاتری دارند؛ پس وارد خدمت شد و رویداد انقضای بعدی بی‌اثر شد.
پرسش دوم: ظرفیت انتظار صفر یعنی هیچ خدمتی نداریم؟ پاسخ: خیر؛ ورود به خدمت‌دهندهٔ آزاد ممکن است. فقط کسی پشت تماسِ فعال منتظر نمی‌ماند.
پرسش سوم: چرا F پس از مهلت بیست تمام شد؟ پاسخ: در نوزده خدمتش شروع شده بود و تحمل فقط انتظار را محدود می‌کند؛ این کد مهلت قطع خدمت ندارد.
پرسش چهارم: چهار خدمت از هفت ورودی، سطح خدمت واقعی است؟ پاسخ: خیر؛ فقط شمارشِ همین دادهٔ تألیفی است. قرارداد سنجه، دادهٔ واقعی و ارزیابی مرکز تماس جدا لازم‌اند.
منابع و مطالعهٔ بیشتر
بررسی منابع: ۲۵ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
