Study On Online Production Order Scheduling And Its Competitive Strategies

Nowadays, most enterprises make their production planning according to customer orders. To beat their competitors in the market, enterprises need to optimize their order scheduling to gain a profit as much as possible. This paper will deal with some kind of scheduling problem where production orders arrive dynamically. The theory of online problem and its competitive strategies is adopted to model the problem. Some fundamental characters on both online strategies and order processing lists are exploited. Basic methods of proving the competitiveness of deterministic strategies are given. According to the variety of the element trait of order, several mathematic models are set up and then online strategies are developed. The main results of the paper are summarized as follows.First, the problem where orders have non-uniform length is studied, which is divided into two subproblems according to the existence of relationship between length and weight of order. For the case where no relationship exists between length and weight, one deterministic strategy TAR , considering weight, length and deadline is proposed. TAR outperforms both ACE (Fung, 05) and LWF (Chan, 04). For example, when the ratio of longest and shortest length of orderâ–³is equal to 1 or 5, the competitive ratio of TAR is equal to 4.56 and 11.11 respectively, while ACE's is 5.0 and 11.47 respectively, and LWF's is 5.0 and 21.0 respectively. It is proved in the paper that no deterministic strategies have competitive ratio less than (?) (â–³/logâ–³), which improves the previous lower boundâ–³. Furthermore, better bounds are given for smallâ–³, i.e., the bounds equal 4.25 and 5.87 respectively for â–³= 2 or 10. For the case that there exists relationship between length and weight of order, two common pricing rules are given and then one appropriate function of weight with respect to length is presented. One deterministic strategy LAS is put forward and proven to be ( Y + 2 Y+ 2)-competitive where Y = 1 +c2 (c 1(1+a)), and c1 , c2 and a are three parameters in the function of weight.Secondly, the problem with uniform length of order is discussed. Three models are considered, including the model of arbitrary weight, the model of uniform weight and the one where pending orders are cancelable. For the first model, a lower bound of 4 is given, improving the previous bound 2.59. Together with the upper bound of 4.56 obtained by TAR , the gap between upper and lower bound is reduced from 2.41 to 0.56. For the model of uniform weight, it is assumed in previous literature that orders have no deadlines or have limitation on earliest due date. Such assumption is not true for actual manufacturing orders, where there is usually a deadline by which orders must be completed. With deadline of order, both non-preemptive and preemptive-restart cases are studied, in which FCFS and PFCFS are proved to be optimal online strategies respectively. The third model where cancellation request is valid to pending orders was firstly proposed by Chan et al., and a 5-competitive deterministic strategy was also provided. It is proved in the paper that no deterministic strategies can be better than 5-compeititve. So, the problem is closed.Thirdly, it is interesting to consider penalty once an order is preempted and then missed. That is, if the manufacturer cannot finish an order in time, he needs to pay a penalty equal to the weight of that order. For the case that no relationship exists between weight and length of order, WSPT (Smith, 1956) and LWF are proved to be O (â–³~2) and ( 8â–³+3/2)-competitive respectively. A new strategy BAC is then presented and proved to be ( 3â–³+ o(â–³))-competitive for ? > 9. On the other hand, two lower bounds of deterministic strategies, 1 .366â–³+0.366 and 6.33 are given forâ–³> 1 andâ–³= 1 respectively. For the case where there exists relationship between weight and length of order, LAS is proved to be ( 3Y + 2+22Y2 +3Y)-competitive. In contrast with the competitive ratio of LAS in the case without penalty, it is easy to see that penalty makes the strategy lose much in competitiveness. Furthermore, a lower bound of Y +2 is given for deterministic strategies in the case.Fourthly, two semi-online cases with different kinds of prediction information are discussed, provided that each order is of uniform length. For the case where the knowledge of largest and smallest weight of order, M and 1 is known beforehand, LWF is proved to be 4[ 1â–³(1/2)k]-competitive where k = logM. An improved heuristic VAR is proposed and proved to be c~*-competitive, whose exact value depends on M . When M =23 or 21 0, c~* is equal to 2.932 and 3.749 respectively, while the competitive ratio of LWF equals 3.5 and 3.938 respectively. Furthermore, c~* is shown to be the lower bound of deterministic strategies. For the case that an online strategy can foresee the order information in a finite time period at any time, it is pointed out that such foreseeing ability cannot improve the performance of deterministic strategies. A randomized strategy RLL is then proposed and proved to be 3 and 3.5-competitive when the length of foreseeing time is equal to 1 and 0.5 respectively, breaking the lower bound of 4 for deterministic strategies.Finally, the paper points out several interesting directions in further work.