奶牛人工授精任務調度模型與算法研究

摘 要：規模化養殖環境下牧場每天都有大量人工授精任務，人工授精任務執行具有最佳時機的特性，研究借鑒“提前/拖期調度”理論建立奶牛人工授精任務調度模型，采用懲罰成本函數兼顧奶牛受孕率和產奶量，采用禁忌搜索算法和二次規劃方法求解人工授精任務執行序列和開始執行時間，預測奶牛排卵時間和最佳人工授精時間。仿真實驗證明了模型和算法的有效性。

關鍵詞：物聯網；人工授精任務調度；提前/拖期；禁忌搜索；二次規劃

中圖分類號：S24 文獻標識碼：A 文章編號：1006-060X（2014）04-0097-04

Abstract： There are many artificial insemination tasks in pasture everyday under large-scale cultivation， and implanting artificial insemination task has the character of optimal timing. The earliness/tardiness scheduling theory was adopted to establish task scheduling model for artificial insemination of dairy cows. Based on the tasks’ conception rate and milk yield， the cost function was proposed. Then the tabu search （TS） and the quadratic programming （QP） was used for processing the sequences of operation and the start time of operation for artificial insemination task， and for predicting the optimal time of artificial insemination. The simulation experiment demonstrated the effectiveness of model and algorithm.

Key words： Internet of Things； artificial insemination task scheduling； earliness/tardiness； tabu search； quadratic programming

商業化奶牛場經營的一個重要目標是使牧場的總利潤最大化[1]。育種決策在奶牛場的管理中發揮了重要的作用。奶牛只有經授精、妊娠、產犢后才能產奶，因此，奶牛的發情檢測和把握恰當的人工授精時機仍然是限制奶牛繁殖效率的主要問題[2-3]。傳統的通過人工檢測奶牛發情已不能滿足現代奶牛場規模化、集約化的養殖需求。物聯網環境下，使用計步器、溫度傳感器等實時監測奶牛的生理特征和運動行為，能高效地監測出發情的奶牛[4]。人工授精必須在奶牛發情周期的特定階段實施，成功率依賴于人工授精時間點的把握[5]。授精過早，公牛凍精容易失活，導致奶牛不能受孕[6]；授精太晚，卵子容易失活，也會導致授精失敗[7]。

規模化養殖環境下，每天都有大量的奶牛發情。受溫度等的影響，奶牛群經常在夜間集中發情。而育種工作者的上班時間是固定的，要做到將所有的奶牛都在恰當的時間進行人工授精比較困難，這也是奶牛受孕率不高的原因。高效的物聯網發情檢測技術能實時檢測發情奶牛并上報人工授精任務，而研究奶牛人工授精任務的優化調度策略，可以綜合提高奶牛人工授精效率。

1 物聯網環境下奶牛育種流程

大規模的奶牛場需要對數千頭乃至上萬頭奶牛進行牛只識別管理和發情檢測，傳統的人工識別方法存在費時費力和準確率不高的問題。物聯網環境下，通過安裝在牛只身體上的體征數據采集終端設備和RFID（radio frequency identification）標簽，實現對奶牛身份的識別和奶牛狀態信息的實時采集。例如，計步器不僅可以準確地監測發情的奶牛，還可以預測奶牛排卵時間和最佳人工授精時間，提高奶牛受孕率[8]。文章中奶牛發情期的開始時刻采用文獻[9]的定義：當奶牛最近6個時段內的平均活動量大于前兩天對應的時段內的平均活動量的2倍時。

牛只管理系統中記錄著奶牛的譜系信息、生產性能信息等，育種工作者要選擇對發情母牛后代改良的各項性狀指標，按照改良指標的性狀進行公牛凍精選擇。當許多牛只發情時，如果沒有運用系統的規劃對奶牛人工授精任務進行科學調度，那將導致人工授精效率的降低和成本的損失。人工授精任務調度還需兼顧奶牛的產奶量和最佳人工授精時間。文章中提出規模化奶牛場人工授精任務調度的方法，合理安排奶牛人工授精任務次序和任務開始執行時間。

2 奶牛人工授精任務調度模型

2.1 提前/拖期調度概述

目前，電子項圈和計步器等檢測記錄了奶牛每天的運動量，根據牛只運動量來檢測出可能發情的奶牛，然后由配種工作者根據奶牛生理發情癥狀、個體生產記錄等再確認是否發情及配種的最佳時間。

研究假設奶牛人工授精任務有最佳的任務完成時間，任務提前完成和拖后完成都會降低奶牛的受孕率，類似于作業車間準時制調度（Just in Time， JIT）問題中的提前/拖期調度（Earliness/Tardiness， E/T）。在JIT調度環境中，作業提前完成或拖期完成都會受到懲罰。因此，一個理想的作業調度計劃目標為：所有作業都在其到期日完成。E/T調度問題求解的是總懲罰成本最小，而文章中的調度問題求解的是人工授精任務的懲罰成本最小化。

Lauff和Werner[10]將E/T調度問題分為單機E/T調度和多機E/T調度，并指出，大多數研究主要考慮單機E/T調度非正則規目標函數的求解，而針對多機E/T調度問題，大部分研究則側重于處理并行機調度問題。在作業車間E/T調度相關研究中，主要運用啟發式算法，如遺傳算法[11-12]、禁忌搜索算法以及數學規劃方法[13-14]等。

2.2 奶牛人工授精任務模型

3 模型求解

為了確保人工授精任務盡量靠近其最優完成時間完成，求解該類問題主要存在的難點是確定配種工作組上人工授精任務執行的序列和任務開始執行時間。

單純使用某一種算法很難同時解決這兩個難點，文章綜合運用禁忌搜索算法（TS）和二次規劃方法（QP）解決這一問題。禁忌搜索算法是一種基于鄰域搜索機制的尋優方法，它通過引入禁忌技術（ 設定禁忌表） 使算法容易跳出局部最優，具有較好的全局尋優能力[15]。而二次規劃則屬于一類精確型的數學方法。TS/QP的處理策略為：先采用EDD（ earliest due date）產生初始解，然后由TS算法提供配種工作組的人工授精任務執行序列，再利用QP優化人工授精任務序列中各任務的開始執行時間。通過TS獲得配種工作組的任務執行序列，為后續的QP求解松弛了調度模型中最難滿足的配種工作能力約束，從而使得QP優化大規模人工授精任務調度的任務開始執行時間成為可能。

3.1 禁忌搜索算法

3.1.1 EDD生成初始解 初始解的產生方式基本上可分為兩種：一是隨機產生； 二是用構造性啟發式方法產生。因為初始解直接影響調度結果的精確性，所以選用構造性啟發式方法產生初始解。采用EDD優先規則，即對各配種工作組的待執行的任務依據各任務的最優完成時間從早到晚排序。

3.1.2 鄰域產生方式 （1）交換操作。交換操作是通過某一配種工作組兩個緊鄰人工授精任務的移動來定義鄰域。移動的宗旨是所選任務向靠近其最優完成時間方向移動，即提前任務與其右側任務交換，而拖期任務與其左側任務交換。這樣可以避免交換（拖期完成，提前完成）的相鄰人工授精任務對，因為交換這類任務對只會促使兩個人工授精任務均背離其最優完成時間，無法改進當前解。同時，為提高搜索效率，需要確保（提前完成，拖期完成）情形的緊鄰人工授精任務對只交換一次。（2）鄰域結構產生方法。步驟1，隨機選擇一個滿足以下條件的人工授精任務u。若人工授精任務u提前完成，且其右側存在相鄰人工授精任務v；若人工授精任務u拖期完成，且其左側存在相鄰人工授精任務v。步驟2，若人工授精任務u提前完成則轉步驟3；若人工授精任務u拖期完成則轉步驟4。步驟3，若人工授精任務u提前完成，則有以下兩種鄰居產生情形：①若人工授精任務v提前完成，則交換（u，v）產生一個鄰居；②若人工授精任務v拖期完成，且未被選擇過，則交換（u，v）產生一個鄰居。步驟4，若人工授精任務u拖期完成，則有以下兩種鄰居產生情形：①若人工授精任務v拖期完成，則交換（u，v）產生一個鄰居；②若人工授精任務提前完成，且v未被選擇過，則交換（u，v）產生一個鄰居。

3.1.3 禁忌對象 為了統一禁忌對象特征，將執行鄰域結構變化前的緊鄰人工授精任務作為禁忌對象。即：如果一個移動是交換緊鄰執行任務對（，） ，則后續搜索重返該任務對的移動在設定的任期內被“禁忌”。

3.1.4 特赦規則 采用基于目標函數值的特赦規則：經過交換操作后，得到既定任務執行序列后，由QP算法求解得到的候選解集中的某個解優于迄今搜索到的最優解時，若該候選解對應于禁忌表中的某個禁忌對象，則從禁忌表中解禁該禁忌對象。

3.1.5 終止準則 終止準則設置為最大迭代次數。

3.2 二次規劃方法

4 仿真實驗

為了測試模型與算法的有效性和效率，對上海一家奶牛場進行了調研，并在此基礎上進行仿真實驗。仿真實驗假設奶牛存欄數為1 000只，奶牛發情的時間和奶牛產奶量隨機產生。奶牛受孕率函數采用文獻[9]的研究結果，設置人工授精任務最優完成時間OCi=12 h，Ti=24 h。每頭奶牛的人工授精時間Pi=30 min。實驗結果表明，當奶牛的發情時間比較分散時，算法求解的調度結果基本可以保證奶牛人工授精任務在靠近最佳時間完成。當奶牛較集中發情時，文章中的模型和算法可以合理分配奶牛人工授精任務的執行順序以及任務開始執行時間，對奶牛人工授精任務問題給出了較好的調度結果。根據實際生產情況， 把人工授精任務到達時間分為ri∈[0：00-12：00]和ri∈[12：00-24：00]兩個時段，任務執行分別為當日[12：00-18：00]和次日[6：00-12：00]，表1列出了一組仿真實驗結果。用大量的隨機排序求解了表1的調度問題，并取20次隨機排序平均值與文章中的算法和EDD算法進行比較。仿真實驗證明了該算法的有效性（表2）。

5 結 語

物聯網技術可以實現對奶牛身份的識別和奶牛發情的實時檢測，并且預測奶牛排卵時間和最佳人工授精時間。規模化、集約化養殖環境下，每天都有大量的奶牛發情且需要人工授精。物聯網技術檢測到發情奶牛的人工授精任務為實時到達，奶牛人工授精任務具有最佳的人工授精時間，并且不同奶牛的產奶量不同，需兼顧不同奶牛人工授精任務的受孕率和產奶量。

文章針對奶牛實際的發情特征，把提前/拖期調度理論方法引入到奶牛人工授精任務調度問題的研究。文章中的求解方法是由EDD產生調度初始解，然后提出禁忌搜索算法和二次規劃方法的混合處理策略，由禁忌搜索算法提供配種工作組的人工授精任務執行序列，然后利用二次規劃方法優化既定人工授精任務序列中各人工授精任務的開始執行時間。仿真實驗證明了該算法的有效性。

參考文獻：

[1] Renkema J A， Stelwagen J. Economic evaluation of replacement rates in dairy herds I. Reduction of replacement rates through improved health[J]. Livestock production science， 1979， 6（1）： 15-27.

[2] Larson L L， Ball P J H. Regulation of estrous cycles in dairy cattle： a review[J]. Theriogenology， 1992， 38（2）： 255-267.

[3] Chebel R C， Santos J E P， Reynolds J P， et al. Factors affecting conception rate after artificial insemination and pregnancy loss in lactating dairy cows[J]. Animal Reproduction Science， 2004， 84（3）： 239-255.

[4] Brehme U， Stollberg U， Holz R， et al. ALT pedometer—New sensor-aided measurement system for improvement in oestrus detection[J]. Computers and electronics in agriculture， 2008， 62（1）： 73-80.

[5] Roelofs J B， Van Eerdenburg F J， Soede N M， et al. Various behavioral signs of estrous and their relationship with time of ovulation in dairy cattle[J]. Theriogenology， 2005， 63（5）： 1366.

[6] Hawk H W. Transport and fate of spermatozoa after insemination of cattle[J]. Journal of dairy science， 1987， 70（7）： 1487-1503.

[7] Hunter R H F， Greve T. Could artificial insemination of cattle be more fruitful？ Penalties associated with ageing eggs[J]. Reproduction in Domestic Animals， 1997， 32（3）： 137-141.

[8] Roelofs J B， van Eerdenburg F J C M， Soede N M， et al. Pedometer readings for estrous detection and as predictor for time of ovulation in dairy cattle[J]. Theriogenology， 2005， 64（8）： 1690-1703.

[9] Maatje K， Loeffler S H， Engel B. Predicting optimal time of insemination in cows that show visual signs of estrus by estimating onset of estrus with pedometers[J]. Journal of dairy science， 1997， 80（6）： 1098-1105.

[10] Lauff V， Werner F. Scheduling with common due date， earliness and tardiness penalties for multimachine problems： a survey[J]. Mathematical and Computer Modelling， 2004， 40（5）： 637-655.

[11] Yang H， Sun Q， Saygin C， et al. Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines： an enhanced genetic algorithm[J]. The International Journal of Advanced Manufacturing Technology， 2012， 61（5-8）： 657-666.

[12] Valente J M S， Moreira M R A， Singh A， et al. Genetic algorithms for single machine scheduling with quadratic earliness and tardiness costs[J]. The International Journal of Advanced Manufacturing Technology， 2011， 54（1-4）： 251-265.

[13] Ronconi D P， Kawamura M S. The single machine earliness and tardiness scheduling problem： lower bounds and a branch-and-bound algorithm[J]. Computational Applied Mathematics， 2010， 29（2）： 107-124.

[14] Baptiste P， Flamini M， Sourd F. Lagrangian bounds for just-in-time job-shop scheduling[J]. Computers Operations Research， 2008， 35（3）： 906-915.

[15] Glover F， Laguna M. Tabu search[M]. Boston： Kluwer academic publishers， 1997.

（責任編輯：賀 藝）