窗時排序定義

交貨期不是一個點而是一個區(qū)間的排序。

《管理科學技術名詞》第一版。 2100433B

第1章緒論 /

11排序問題的背景及描述 /

12現(xiàn)代排序 /

13算法中的幾個重要概念 /

14準時排序及相關結果 /

15窗時排序及相關結果 /

16符號表示 /

17本書的貢獻與組織結構 /

第2章最小化提前/延誤的賦權工件個數(shù) /

21引言 /

22交貨期窗口的位置待定 /

23交貨期窗口的大小待定 /

24交貨期窗口的位置和大小均待定 /

25給定的交貨期窗口 /

26推廣到多臺平行機 /

27結語 /

第3章最小化提前和延誤時間懲罰 /

31引言 /

32交貨期窗口給定 /

33交貨期窗口的位置待定 /

34多個綜合目標 /

35推廣到多臺機器 /

36結語 /

第4章有交貨期窗口的無界批處理 /

41批處理問題 /

42相關研究結果 /

43給定的交貨期窗口 /

44交貨期窗口的位置待定 /

45結語 /

第5章關于非準時工件數(shù)的有界批處理 /

51問題描述 /

52最優(yōu)性質 /

生產調度是根據(jù)企業(yè)生產系統(tǒng)的生產目標和環(huán)境狀態(tài)，在盡可能滿足約束條件（如交貨期、工藝要求和路線、資源現(xiàn)狀）的前提下，按照工藝規(guī)程和計劃，通過下達生產計劃及調度指令對系統(tǒng)內的可用資源進行實時任務分配，以達到縮短產品的制造周期、減少在制品、降低庫存、提高生產資源的利用率及提高制造系統(tǒng)生產率等目的。

影響生產調度問題的因素很多，正常情況下有產品的投產期、交貨期（完成期）、生產能力、加工順序、加工設備和原料的可用性、批量大小、加工路徑、成本限制等，這些都是所謂的約束條件。有些約束條件是必須要滿足的，如交貨期、生產能力等，而有些達到一定的滿意度即可，如生產成本等。

為了避免儲存及隱藏的額外運轉帶來的高費用，例如，由于等待、傳遞、額外勞動力、重加工及訂單改變等引起的效益損失，生產商不僅考慮延誤帶來的懲罰還必須顧及提前完工付出的費用，這就是準時排序問題。它限定工件的交貨期：如果工件在交貨期之前完工，會出現(xiàn)儲存費和保管費之類；而在交貨期之后完成，固然要科以罰款，則會產生延誤賠償甚至失去合作機會等損失。而準時排序的目的就是要小化這些費用之和，所以，在“準時”概念中，盡可能使得工件的完工時間接近其交貨期或者提前和延誤的工件個數(shù)盡量少。因此，提前和延誤應該盡可能地避免，這也使得以前討論的傳統(tǒng)性能函數(shù)無效。既然目標函數(shù)是關于工件完工時間的非正則函數(shù)，問題的研究相對比較困難。

現(xiàn)實中，供應商和客戶在簽訂供應合同時，通常會指定一個交貨時間區(qū)間，如果工件在這個時間區(qū)間內完成則被認為是準時的，不會招致任何處罰。它是將交貨期合理地設置成一個時間段，而不再是單個時間點，這種排序稱為窗時排序。我們把這個時間區(qū)間稱為工件的交貨期窗口，該窗口的左端為早交貨期（或稱“交貨期窗口的位置”）、右端為晚交貨期。如果工件在窗時交貨期前完成，則必須被庫存，這種情況視為一個提前處罰。另外，如果工件在交貨期窗口后完成，根據(jù)合同中的規(guī)定，它將導致延遲懲罰。顯然，如果交貨期窗口較大則可以增加供應商生產和輸送的靈活性。然而，設置大型的交貨期窗口和延遲工件完成時間都會降低供應商的競爭力和客戶服務水平。所以交貨期窗口的設置也經(jīng)常成為問題的目標之一。

本書探討的內容都是對經(jīng)典排序的突破，研究現(xiàn)代排序與準時、窗時排序的結合應用，目的是為了在新型排序環(huán)境下，使某個衡量函數(shù)大或者小，如提前時間、延誤時間、提前或延誤的工件個數(shù)及交貨期窗口的確定等 "

二叉排序樹(Binary Sort Tree：BST)

1、二叉排序樹的定義

二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：

①若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；

②若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；

③左、右子樹本身又各是一棵二叉排序樹。

上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。

2、二叉排序樹的特點

由BST性質可得：

（1） 二叉排序樹中任一結點x，其左(右)子樹中任一結點y(若存在)的關鍵字必小(大)于x的關鍵字。

（2） 二叉排序樹中，各結點關鍵字是惟一的。

注意：

實際應用中，不能保證被查找的數(shù)據(jù)集中各元素的關鍵字互不相同，所以可將二叉排序樹定義中BST性質(1)里的"小于"改為"小于等于"，或將BST性質(2)里的"大于"改為"大于等于"，甚至可同時修改這兩個性質。

（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。

【例】下圖所示的兩棵樹均是二叉排序樹，它們的中序序列均為有序序列：2，3，4，5，7，8。

3、二叉排序樹的存儲結構

typedef int KeyType； //假定關鍵字類型為整數(shù)

typedef struct node { //結點類型

KeyType key； //關鍵字項

InfoType otherinfo； //其它數(shù)據(jù)域，InfoType視應用情況而定，下面不處理它

struct node *lchild，*rchild，*parent； //左右孩子指針

} BSTNode；

typedef BSTNode *BSTree； //BSTree是二叉排序樹的類型

二叉排序樹的基本操作（pascal）：

1.中序遍歷所有元素

procedure tree_walk(x:longint);

begin

if x<>0 then

begin

tree_walk(left[x]);

write(key[x]);

tree_walk(right[x]);

end;

2.查找給定的元素

function tree_search(x,k:longint):longint;

begin

if (x=0) or (k=key[x]) then exit(x);

if k

end;

非遞歸版本

function tree_search(x,k:longint):longint;

begin

while (x<>0) and (k<>key[x]) do

begin

if k

end;

exit(x);

end;

3.查找最小元素

function tree_minimum(x:longint):longint;

begin

while left[x]<>0 do

x:=left[x]；

exit(x);

end;

查找最大元素

function tree_maximum(x:longint):longint;

begin

while right[x]<>0 do

x:=right[x];

exit(x);

end;

4. 求后繼

function tree_successor(x:longint):longint;

var

y:longint;

begin

if right[x]<>0 then exit(tree_minimum(right[x]));//若右子樹不空，則返回右子樹中的最小值

y:=p[x];//若右子樹為空，則后繼y為x的最低祖先節(jié)點，且y的左兒子也是x的祖先

while (y<>0) and (x=right[y]) do

begin

x:=y;

y:=p[y];

end;

exit(y);//注意，若y為0，則x無后繼

end;

//注意，函數(shù)返回值為節(jié)點編號，并不是節(jié)點本身的值

5.插入

procedure tree_insert(z:longint);//注意z為節(jié)點編號，并非樹中的值

var

x,y:longint;

begin

y:=0;

x:=root;

while x<>0 do//查找z的父節(jié)點，y記錄

begin

y:=x;

if key[z]

end;

p[x]:=y;

if y=0 then root:=z//若z為根節(jié)點

else begin

if key[z]

end;

end;

6.刪除

刪除操作是最麻煩的，分3種情況：

（1）若z無子樹，則就刪除z節(jié)點，更新p[z]的值為空

（2）若z有一個子樹，刪除z節(jié)點，更新p[z]的值為z的兒子節(jié)點，更新left[p[z]] 或 right[p[z]]

（3）若z有兩棵子樹，先找到z的后繼y（后繼節(jié)點無左子樹，可證），刪除y節(jié)點，更新p[y]與left[p[y]] 或 right[p[y]],最后用節(jié)點y的數(shù)據(jù)覆蓋z節(jié)點

procedure tree_delete(z:longint);

var

x,y:longint;

begin

if (left[z]=0) or (right[z]=0) then y:=z

else y:=tree_successor(z);

if left[y]<>0 then x:=left[y]

else x:=right[y];

if x<>0 then p[x]:=p[y];

if p[y]=0 then root:=x

else begin

if y=left[p[y]] then left[p[y]]:=x

else right[p[y]]:=x;

end;

if z<>y then key[z]:=key[y];

end;

7.查找數(shù)中第k大元素

需要對每個節(jié)點新開一個域v[x]，記錄該節(jié)點的有多少子節(jié)點，

查找時分三種情況：

（1）k=v[left[x]] 1 則當前x節(jié)點為所求

（2）k<=v[left[x]] 則在左子樹中繼續(xù)查找

（3）k>v[left[x]] 1 則在右子樹中繼續(xù)查找,k更新為k-left[x]-1;

function find(x,k:longint):longint;

begin

if v[left[x]] 1=k then exit(key[k])

else if v[left[x]]>=k then exit(find(left[x],k))

else exit(find(right[x],k-v[left[x]]-1));

end;