Order Sequencing and Capacity Balancing in Synchronous Manufacturing

Keywords: SYNCHRONOUS MANUFACTURING, SEQUENCING, ORDER RELEASE, HEURISTICS, INTEGER SYNCHRONOUS MANUFACTURING, SEQUENCING Synchronous manufacturing, order release, sequencing, heuristics, integer programming 1

Synchronous manufacturing aims at achieving the benefits of intermittent production lines in production situations that operate without lines. Benefits such as short and constant throughput times and predictable capacity loading can be acquired through an appropriate design of the synchronous manufacturing system and its control system. The order release mechanism is an essential part of this control system. It determines the sequence in which orders are released to the shop floor. As orders may differ in the amount and distribution of their capacity requirements over subsequent production stages, total capacity load may vary over time. If the available capacity per period is not flexible, capacity balancing becomes an issue in the order release decision. In practice, heuristics or rules of thumb are used to solve this problem, but their effectiveness is questioned. This paper examines the effectiveness of some new heuristics that are based on insights from assembly system design and work load control, and compare their performance with an optimal solution approach. The approaches are evaluated in a rolling schedule environment, and under different levels of capacity fluctuations and problem sizes. The results show that the performance of the heuristic solutions deteriorates if capacity fluctuations between the stages increase. If we measure both the amount and frequency of shortages over a long period of time in a rolling schedule environment, a quite simple rule that only takes the available capacity during the first stage into account outperforms more intelligent rules.

Synchronous manufacturing is a concept that is behind several popular shop floor management approaches, such as Lean and Quick Response Manufacturing. The basic idea is to create a flow of work through the manufacturing system, either continuous or intermittent, in order to achieve short and constant throughput times and a predictable loading of the resources in the system. Both the structure of the production system and the control system are to be designed such that this flow can be achieved [START_REF] Schmenner | On theory in operations management[END_REF]. One of the earliest and most famous synchronization methods is single product assembly line balancing (see [START_REF] Scholl | State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[END_REF] for an overview). The production system is designed as a connected line, progress control is eliminated at all, and the order release decision reduces to the decision on the cycle time of the line, i.e. the time between subsequent releases. The concept was applied first in the high volume automobile plant of Henry Ford. As changing the cycle time (a control decision) may require a different design of the production line (i.e., number of stations and assignment of tasks), the relation between both design decisions is central in the assembly line balancing problem. More recent approaches give attention to the issues in case the manufacturing process is not connected as a single product line. For multi-product lines, the concept of assembly line balancing has been extended to mixed and multi model assembly line balancing and generalized [START_REF] Becker | A survey on problems and methods in generalized assembly line balancing[END_REF]. If the product(s) are no longer produced within a single line but in several stages of production, a control system can be used to connect several autonomous parts of the manufacturing system. Period Batch Control (PBC) [START_REF] Burbidge | The principles of production control[END_REF][START_REF] Burbidge | Period Batch Control[END_REF][START_REF] Benders | Period batch control: classic, not outdated[END_REF] is to be considered as the earliest example in this category. PBC An illustration of the order sequencing and capacity balancing problem is found in the longitudinal study of Süer (see e.g. [START_REF] Süer | Operation and control of cellular systems at Avon Lomalinda, Puerto Rico[END_REF]Gonzalez 1993, Süer 1998) on a jewellery firm. Production of jewellery requires similar operations for various product types, such as earrings, rings, bracelets and chains. The processing plans may vary per product type in terms of type of plating. Most operations are performed manually, using simple tools, small machines and equipment. Examples are casting, cleaning, and tumbling. The employees of a cell have been trained to perform all tasks in all stages of the production process. Speed differences between employees are minor. Capacity management is therefore mainly oriented towards work force scheduling, and hiring/firing decisions. The firm operates in synchronous manufacturing mode. The stages represent a subset of operations that are to be performed within a single period of time (four hours in case of the jewellery firm). At the end of each period, the various subsets of operations all need to be completed, as all jobs that are in progress are transferred to their next stage at the same moment in time. At such a transfer moment, employees may have to switch to other tasks within the cell. Some operations, such as tumbling and plating, are necessarily performed in batch. The minimal throughput time for a batch of products determines the length of the period that can be used in a synchronous manufacturing system. The cell starts each period with a new order that is selected from a list of orders that should be completed during the cycle (i.e., at the end of the week). The batch size, process plans, and work content per stage may differ per order. Therefore, capacity requirements may vary strongly, both per order and per stage. The expected throughput time of a batch within a stage is a function of the number of employees allocated to this stage. In a synchronous manufacturing system, the minimal number of employees required in each stage in order to finish this batch within the end of each period can be calculated.

An important problem faced in such synchronous manufacturing systems concerns the capacity balance over time [START_REF] Cesani | A study of labor assignment flexibility in cellular manufacturing systems[END_REF]. A cellular system makes it less appropriate to vary the total number of employees over time. Employees should feel themselves responsible for the whole task of the cell. A relatively constant number of employees over various periods is therefore preferred. There are two planning decisions that affect the objective of achieving a uniform loading of total capacity in multi-model systems. The batch-size decision, and the order sequencing or release decision [START_REF] Karabati | Assembly line balancing in a mixed-model sequencing environment with synchronous transfers[END_REF]. This paper will give attention to the latter decision. The release decision can be supported either by intelligent design of an order sequencing heuristic, or by creating beforehand one or more feasible order release sequences from which the cell can choose. This paper compares these two approaches for direct support of the order release decision.

Illustrative example

Table 1 presents a realistic example with 10 orders that have to be released during one week. We have 10 orders (A,…,J) and five stages j=1,…,5. An order that starts in period t=1 in stage j=1 arrives in period t=2 in stage j=2, and leaves the system at the end of period t=5, if stage j=5 has been finished. Orders are represented using different shades. The amount of capacity required in a stage differs per order and is presented in the cells of the table . A row shows the fluctuating capacity requirements of that stage. Orders may also require a different total number of employees (i.e. the sum of the cells with identical shade). However, the sum of the cells in the same column is more important for the capacity management of the firm. This shows the total number of employees needed in a single period. If this number exceeds the available capacity, the firm has to hire additional employees or change the sequence of orders. The problem is to determine one or more sequences for the orders A,…,J such that the available capacity of 20 employees in each period t is not exceeded as long as possible. For the first four periods, earlier decisions on the sequence in a previous week affect the loading of the available capacity. The cells at the bottom-left side express the capacity requirements of these already started orders that still have to complete one or more stages. The same effect appears at the end of the week, as the last four orders in the sequence affect not only capacity in this week, but also capacity requirements in the next week. Here the end-of-horizon effect or truncated-horizon effect appears (see e.g. [START_REF] Baker | An experimental study of the effectiveness of rolling schedules in production planning[END_REF][START_REF] Stadler | Improved rolling schedules for the dynamic single-level lot-sizing problem[END_REF].

***INSERT TABLE 1 ABOUT HERE***
Literature uses various approaches to cope with the end-of-horizon effect. Some papers (e.g., [START_REF] Ding | An effective mixed-model assembly line sequencing heuristic for Just-In-Time production systems[END_REF][START_REF] Lee | Workforce planning in mixed model assembly systems[END_REF][START_REF] Ouenniche | Sequencing, lot sizing and scheduling of several products in job shops: the common cycle approach[END_REF] totally neglect the end-of-horizon effect.

Others (e.g., [START_REF] Karabati | Assembly line balancing in a mixed-model sequencing environment with synchronous transfers[END_REF]Sayin 2003, Vairaktarakis and[START_REF] Vairaktarakis | Complexity of workforce scheduling in transfer lines[END_REF] assume that exactly the same order release pattern will be repeated during the next week. These methods do not address the end-of-horizon effect in a realistic way. [START_REF] Gronalt | Workforce planning and allocation for mid-volume truck manufacturing: a case study[END_REF] introduce the overall average worker assignment in their numerical experiments. We propose a slightly different approach that uses the stage-average capacity requirements as capacity load factor if the actual capacity load is unknown. According to [START_REF] Stadler | Improved rolling schedules for the dynamic single-level lot-sizing problem[END_REF], this provides a terminal condition that improves the quality of the solutions in a rolling schedule environment. The upperright side of Table 1 shows the average required capacity per stage. For example, stage j=1 has an average capacity load of ( ) + + + + + + + + + = 3 5 3 2 2 3 2 4 3 6 10 3.3 employees, which is used to estimate the load in stage j=1 in periods t=11-14. Note that in Table 1 no order exceeds the capacity limit of 20 employees. For example, order A requires 3+5+4+6+2=20, and J requires 6+2+2+2+2=14 employees. The mean required capacity per order equals 18.6 employees. The loading should result in a sequence for which the available capacity per period is not exceeded. The sequence presented in

1 max 0, m tj t j Y AC = - ∑ t=1,…,n+m-1
The problem can now be formulated as:

Given:

• a set of i=1,…,n orders that have to start during periods t=1,…,n;

• their capacity requirements ij C during j=1,…,m stages of completion;

• the capacity requirements

+ - = = ⋅ ∀ = ∀ = ∑ (1)
Analogues to job scheduling, this problem can be viewed as a weighted tardiness problem, where tardiness is not related to exceeding the due date of a job but to exceeding the available capacity in a period. Morton and Pentico (1993: p. 54) denote that problems using this objective are very difficult to solve exactly. The complexity of this problem has not yet been determined, but similar problems that are discussed in [START_REF] Vairaktarakis | Complexity of workforce scheduling in transfer lines[END_REF] are NP complete in the strong sense for situations with the number of stages m greater or equal to three.

Order release heuristics

This section describes several single pass heuristics to determine a sequence of orders for release. Single pass heuristics do not reconsider decisions taken during the procedure. The heuristics are based on insights from assembly system design and work load control. We will introduce the heuristics and show the results of applying the heuristic on the data of Table 1.

FillCap

This heuristic is actually being applied in the jewellery firm. It chooses at the start of period t from the set of assignable orders the order that maximally fills capacity in that period. The set of assignable orders contains all orders that still have to be released and have a capacity requirement in stage j=1 nearest to but not exceeding the available capacity. If there are more orders to select from, it chooses randomly. We denote this heuristic as FillCap. See the Appendix for a pseudo-coded description of the heuristic.

From Table 2 we see that the heuristic FillCap does not take into account the effect of a selected order on the available capacity for the next m-1 periods. As a consequence, in period 9 a capacity shortage occurs.

*** INSERT TABLE 2 ABOUT HERE ***

AvgLoad

The AvgLoad heuristic applies the principle of bottleneck loading that is known from mixed model assembly line balancing (e.g. Askin and Standridge 1993: 56-59). The idea is to select the job that will result in a future load on the bottleneck as close to its average rate as possible. Each new assignment will try to correct the gap between the average rate and the cumulative load on the bottleneck that has resulted from earlier assignments.

The bottleneck of this synchronous manufacturing system is not a single stage, as is usually the case in mixed model line assembly problems, but the number of employees available. The heuristic should select an order that (if possible) can be assigned to the first period and that brings the total released workload as close as possible to the long time average. The calculation of the long time average uses all information available, i.e. the load of the set orders to be released in this cycle (each order requires on average 18.6 employee periods) and the load of the already released orders from the former cycle (these four orders generate a total workload of 37 employee periods during 10 buckets (4+3+2+1). As each order generates workload during 5 buckets (m=5 stages), the backlog from the preceding cycle corresponds to 2 complete orders. The average load of an order on the bottleneck equals (10*18.6 + 37) / (10+2) = 18.58 employees per order. So for the first release decision, we would like to choose an order with a total workload as near as possible to the average rate minus already released load, i.e. 3*18.58-37 = 18.75. After selecting the order (either D or I), the load aimed at for the next release decision is calculated. We denote this heuristic as AvgLoad. See Table 2 for the results in the example problem.

StageLoad

The heuristic StageLoad aims at achieving a balanced workload distribution over the stages. It is based on insights from the field of workload control [START_REF] Land | Workload control concepts in job shops: a critical assessment[END_REF][START_REF] Riezebos | Improving a practical DBR buffering approach using Workload Control[END_REF][START_REF] Stevenson | A review of production planning and control: the applicability of key concepts to the make-to-order industry[END_REF]. It searches for an order that fits best within the expected peaks and troughs of the already generated workload distribution from the past assignments. The order to be selected should have a dissimilar workload pattern as compared to the already generated pattern. This generates a less variable stageload pattern, which also reduces the variability of the sum of the m stageloads. In this way we might be able to avoid suddenly appearing large fluctuations in the required number of employees.

StageLoad considers the release of one order as a release of m separate workloads for the stages. Each one of them should receive a workload that brings the total as close to the desired average amount as possible. StageLoad selects the order that minimizes the sum of these m quadratic distances. The sum of squares in the first step of StageLoad is minimal for order C, so C is chosen. See Table 2 for the results on the example problem. By choosing the order with minimal quadratic sum of distances to the average stage loads, the creation of sudden peaks and troughs in capacity load is avoided. However, this does not guarantee that sufficient capacity will always be available. For example, in period 4 order B is selected, as this order realizes the best stage load distribution, but this order creates a conflict with the available capacity in period 4.

AvailStageLoad

The fourth heuristic tries to avoid the conflicts with available capacity and applies the StageLoad heuristic only to the set of orders that fit within the available capacity. Note that the FillCap and AvgLoad heuristic do the same. If no orders fit within the available capacity, the whole set of unassigned orders is used to determine the order that fits best. The heuristic AvailStageLoad therefore combines the two approaches.

The results of the heuristic AvailStageLoad in the example problem are exactly equal to heuristic StageLoad, as in each stage the preferred order belongs to the set of orders from which it should be chosen (see Table 2). In general, the performance of heuristic AvailStageLoad is expected to be better than heuristic StageLoad.

The computational complexity of all four heuristics is ( )

2
O n , as in a single pass heuristic the whole cycle is repeated n-1 times, and step 2-3 is of order n. The first heuristic FillCap is a simple straightforward rule. The other three are more sophisticated in their computations, as they aim at achieving not only a short-term advantage, but a long-term balance as well. However, they allow a lower than possible fill in the current period in order to achieve the long-term balance. No guarantee is given that any of the heuristics is able to find an optimal solution. For the example problem, all four heuristics were unable to find an order sequence without violating the capacity constraint in at least one period. This raises the question on the possibility of finding a sequence that results in a feasible solution. The total number of sequences is n!. Complete enumeration is therefore no realistic alternative for large n. However, the advantages of a good order sequence for the productivity and acceptance of this synchronous manufacturing system makes it worthwhile to search for an improved solution procedure. The next section will proceed with such a procedure.

4

A mathematical model to support the order release decision

This section discusses a mathematical model that generates an optimal order sequence for all orders that have to be released in the cycle. The mathematical model is as follows:

F
+ - = ⋅ = ∀ = = ∀ = = ∀ = ∀ = ∑ ∑ ∑ 1,
+ - = - = ∀ = + + - ∀ = - = ⋅ ∀ = ∀ = ∑ [ ] 1 , (
m tj t t j it t tj m Y CS AC t n m X CS Y = - ≤ ∀ = + - ∈ ≥ ≥ ∑
This mathematical model uses it X as binary decision variable, indicating that order i starts in period t whenever the variable has value 1. The other variables are non-negative and continuous (see ( 9)). Constraints (3) and ( 4) guarantee that a feasible assignment is obtained. The third constraint (5) shows that we use this model in a rolling schedule environment, as we take the effects of the release decisions in the former cycle into account in the current decision. Constraint (6) calculates the consequences for future periods that will be affected by the current decision. We use the average load in a stage if the actual load is not being determined in the current decision round. Constraint (7) determines the consequences of the release decision for the stage load in subsequent periods and is similar to Formula (1). Constraint (8) calculates the capacity shortage per period. The objective function (2) minimizes a weighted sum of the capacity shortages over time. Through the use of positive weights < 1 for periods behind the sequence horizon, the end of horizon effect (Stadtler 2000) is avoided. Most sequencing algorithms that are known from assembly line balancing [START_REF] Scholl | State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[END_REF] or suggested for synchronous systems (e.g. Vairaktarakis et al. 2002, Gronalt and[START_REF] Gronalt | Workforce planning and allocation for mid-volume truck manufacturing: a case study[END_REF] do not treat the end-of-horizon problem. As a result, infeasible solutions may be encountered at the next decision moment. Sometimes the special case of a cyclic schedule [START_REF] Vairaktarakis | Complexity of workforce scheduling in transfer lines[END_REF] is used to tackle this problem. Our mathematical model avoids this effect by taking into consideration that the loading in the periods behind the horizon should not exceed the on-average available remaining capacity. Note that the proposed mathematical model is rather easy to read due to the introduction of the intermediate variable tj Y . This holds especially true for modelling the stage load resulting from the release sequence (7).

The model has been implemented in Lingo in order to find a solution for the problem of Table 1. As weights we selected 1 ; 0.5 t t w for t n w for t n = ≤ = > . The last column of Table 2 shows the results. During the first ten periods no shortages occur, neither are they expected for the periods 11-14, i.e. for the periods behind the sequence horizon. Hence we conclude that none of the four heuristics achieved an optimal result. The question is whether there are differences in the performance between these heuristics.

Experimental design

The former sections have introduced the four heuristics and the mathematical model and illustrated their performance using a realistic example. We would like to extend this comparison to a rolling schedule context, as this is the usual situation where such a solution procedure is being applied in synchronous manufacturing systems.

The basic premise we would like to test is whether the solution approaches perform different when the distribution of workload over the stages changes ( ( )

2 ij C MixVar f σ =
) or the variation in the total workload per order increases (

1 2 m ij j C VolVar f σ =   =   ∑  
). The first is a mix-oriented factor, while the second is a volumeoriented factor. In addition, we would like to test whether the performance of the approaches under these experimental settings changes if production characteristics (the number of stages m) or planning characteristics (the schedule horizon n) are modified. For each cycle a random problem is generated with n orders and m stages. The total workload per order and the distribution of this workload over the stages varies randomly according to the specified factorial design of the experiment. The problem that has to be solved consists of determining a sequence for the orders.

The consequence of the chosen sequence is input to the scheduling problem of the same solution approach for the next cycle, as we test the approaches in a rolling scheduling environment. So, although the approaches receive the same set of new orders at the start of a new cycle, only the first sequencing problem in a replication is completely identical for all solution approaches. Since we do not know if the size of the problem matters, we have tested the approaches using low and high values for both the scheduling horizon/number of orders n and the number of stages m.

In total 4*4*100*50 = 80000 sets of orders were generated and the five solution approaches solved the resulting problems.

We evaluate the approaches first on the average total capacity shortage per cycle. This is a kind of tardiness measure, as capacity shortage is zero if there is overcapacity in every bucket. For each bucket t=1,…,n we calculate the capacity shortage t CS and add it to the total capacity shortage in that cycle. The average total capacity shortage is calculated over the number of cycles in the rolling schedule. Secondly, the frequency of a shortage in a schedule of one cycle is measured. If in any of the buckets a shortage occurs, this cycle is counted as one with shortages. The mean frequency per replication of 50 runs was calculated. This performance indicator shows how often a schedule that is constructed with this approach will face a shortage. The ratio of the two performance indicators (Exp.Shortage = Shortage / Frequency) reveals the mean total amount of capacity short in a cycle that faces a shortage. Available capacity is constant at 20 units per period. Average capacity requirement per order is also constant and set at 18 for all configurations. At a low volume variation, the actual capacity requirement is 18 ± 1, while a high volume variation has actual requirements equal to 18 ± 3. The capacity requirement of an order is therefore either in the interval [17,19] or [15,21], depending on the value of VolVar. We use a uniform distribution within an interval, so each element in the set has equal probability. As the maximal mix variation in a stage, MV, may change in the course of the procedure, we first select randomly a stage and next determine the number of units in that stage. This number has to be at least one, as described in the sampling procedure (see Appendix). The problem generator and the five solution approaches have been programmed in Delphi 6, where the procedure that determines the optimal solution to the mixed integer programming problem uses the dll of the Lingo 5 solver. Generating these 80000 problems and solving them with the five solution approaches took 37.4 hours CPU time on a 2.4 GHz Pentium IV PC running Windows XP, the majority of it being used by the optimization approach. The average CPU time of solving a problem to optimality was 1.5 seconds. The

Expectations with respect to the results

The solution approaches are expected to perform differently according to the variation in the experimental design factors. We number our expectations in order to enable testing in the next Section.

(i) The heuristic FillCap is expected to perform better if MixVar is high instead of low.

(ii) The effect of an increased variation in the total workload (VolVar high) on the performance of FillCap is uncertain. The reason for (i) is that a high MixVar will result in a higher chance of orders available that fit within the available capacity, even if the amount of capacity available is small.

(iii) Compared to FillCap, AvgLoad is on average expected to result in a lower shortage, while frequency is not changed (iv) AvgLoad will perform better if MixVar is low instead of high. (v) AvgLoad will be more effective if VolVar is high.

The heuristic AvgLoad improves the selection procedure of FillCap, but allows idle time earlier in the cycle as it favours a total workload near the average load on the bottleneck. The effect of an increased variation in the total workload (VolVar high) on the performance of FillCap is uncertain. The reason for (iv) is that AvgLoad does not take the distribution of workload over the stages into account. A higher variation in this distribution will result in relatively more shortages. Further, as it aims at balancing the total volume, it will be more effective if VolVar is high (v).

(vi) StageLoad is not effective in managing shortage and frequency. (vii) StageLoad is more effective for high MixVar.

We do not expect the heuristic StageLoad to be effective in managing shortage and frequency (vi), as it allows choosing an order while knowing that a shortage occurs. However, it might result in a more stable loading of the stages, which is more effective for high MixVar (vii).

(viii) AvailStageLoad is expected to perform better than StageLoad (ix) AvailStageload is more effective if MixVar is high. The heuristic AvailStageLoad uses the basic idea of StageLoad in selecting an appropriate order that fits in the available capacity. It is expected to perform better than StageLoad (viii) and improve if MixVar is high (ix).

(x) Zero shortage solutions are less easy to find in case either MixVar or VolVar is high. In case either MixVar or VolVar is high, we expect that it will be more difficult to find a solution with zero shortage (x).

(xi) Both the average shortage per cycle as the frequency of shortages will increase if n increases. (xii) The average shortage per bucket decreases if n increases. (xiii) Only StageLoad and AvailStageLoad benefit from an increase in m.

The experimental variable n is expected to have an equal effect on all approaches. If the length of the horizon n increases, both the average shortage per cycle and the frequency of shortages are expected to increase (xi). However, longer cycles (n↑) means a larger set of orders to select for release, and hence more possibilities to reduce or avoid shortages. So the increase might not be proportional to the increase in n, in other words the average shortage per bucket might decrease (xii). More stages (m↑) increases the sensitivity for unbalances between the stages. We therefore expect a performance improvement only for the heuristics that take this into account (i.e., StageLoad and AvailStageLoad) (xiii). Next subsection will describe the results of the experiments, which enables us to determine if these expectations are valid.

Results

The results of the experiments were analyzed on differences in the mean performance. We used ANOVA to test whether the means were equal or not. Table 4 shows significant differences with respect to the mean shortage for all main effects and all interaction effects except one. Most contributing to differences in the mean are MixVar, Approach, and the combined effect of these two factors. For the frequency of shortages, the same factors are most important in explaining the total variation. Note that the size of the problem (n and m) has a significant, but minor contribution to explaining the variance in the data. We conclude that the mean performance of the various approaches cannot be assumed to be equal for all factorial levels.

***INSERT TABLE 4 ABOUT HERE***

In order to see if the performance of all approaches differs significantly (expectations iii, vi, and viii), we applied multiple comparisons and tested for significant differences using the Tamhane test statistic. Table 5 shows the results of this comparison. The type of approach used shows up to be a highly significant factor, as the difference with all other approaches is significant. We only present the differences between Optimal and the other approaches, but the same holds true for the remaining comparisons. Note that Table 5 presents the average differences, based on all values of the experimental variables n, m, VolVar, and MixVar.

***INSERT TABLE 5 ABOUT HERE***

The optimal solution clearly outperforms the other heuristics. The difference in mean shortage with FillCap equals 2.762 employee periods per cycle, while the frequency of cycles with a shortage is 43.7% higher, as can be seen from Table 5 (column Mean Difference (I-J)). AvgLoad performs even worse -contrary to what we expected in (iii), but still better than the AvailStageLoad heuristic. The StageLoad heuristic performs worst, as was expected in (vi) and (viii)). However, the good performance results of FillCap were not expected at all. For all factorial levels, the less sophisticated FillCap appears to be significantly better than the other heuristics that aim at an improved selection process. FillCap just chooses the order that fills the available capacity in the first stage, and this results both in a lower average capacity shortage and less frequent shortages than more sophisticated heuristic selection procedures. Sophistication in these single pass heuristics does not seem to be of value.

***INSERT TABLE 6 ABOUT HERE***

The question now remains how the solution approaches perform at the two levels of the experimental factors.

The descriptive statistics in Table 6 show that an increase in MixVar has a much stronger impact on the extra capacity required and the frequency of shortages than an increase in the variation in the total workload of an order (VolVar). However, this holds only true for the heuristic approaches, as the optimal solution is completely insensitive for changes in these experimental factors. For each row in Table 6, 5000 problems have been solved (80000 in total), and the number of problems that did result in a shortage in the optimal solution was zero. Hence, expectation (x) cannot be confirmed. The performance difference between the heuristic approaches depends on the settings of the experimental factors. Figure 2 shows that a change in MixVar results in slightly different gradients of the curves that represent the five solution approaches. Hence, relative performance of the heuristics if compared with each other changes if MixVar changes. However, (i), (iv), and (ix) do not hold, as the absolute performance of all heuristics deteriorates for high MixVar, while expectation (iv) can be confirmed. And even for the relative performance improvement in average shortage, FillCap is better than the other heuristics.

***INSERT FIGURE 2 ABOUT HERE*** The results show that the difference between heuristics and the optimal solution is high. Figure 2 shows that if MixVar is low, the mean frequency of shortages during a cycle is between 20% and 55% if the heuristics are being used, and increases to 60%-95% if MixVar is high, while the optimal solution approach is still able to find a solution without shortages. The frequency of shortages equals zero if the optimal solution approach is used. The required CPU time for obtaining the optimal solution is less than 10 seconds, with an average of 1.5 seconds. Therefore, the use of the optimal solution approach is a realistic alternative if the size of the problem is restricted and leads to substantial savings and an improved capacity balance. Note that the size of problems considered in this study is realistic for many real life situations. Note also that in our experiments the optimal solution was insensitive to the value of the parameter t w =0.5, as a trade off between short term and long term effects could be avoided (the optimal solution was always able to avoid overtime). Table 6 shows that VolVar has less effect on the heuristics. FillCap is indeed relatively insensitive to changes in VolVar, which confirms (ii), but AvgLoad is not performing better for high VolVar, as expected in (v). Finally, we take a look at the effect of the parameters n and m. An increase in the number of periods per cycle decreases the performance, and hence expectation (xi) is confirmed. However, in case of low mix variation, the effect is very small. That means that the average shortage per bucket decreases if n increases (xii). Apparently, longer cycles actually make capacity balancing more effective. With respect to an increase in m, a strange phenomenon appears. The direction of the effect depends on the value of MixVar. If MixVar is low, an increase in m deteriorates the performance of the heuristics, but if MixVar is high, an increase in m improves the performance of all heuristics. Therefore, expectation (xiii) is not confirmed. There is an effect for all heuristics if m changes, but we have to accommodate for the interaction effect with MixVar. Note that Table 4 already showed that this interaction is important, especially for explaining the variance in the shortage performance measure.

Conclusions

The concept of synchronous manufacturing is behind several popular shop floor management approaches. It aims at achieving short and reliable throughput times through the introduction of fixed transfer moments between several stages of production. This causes a loading of the resources that can be predicted in advance, which makes it easier for planners to do their job. If capacity requirements fluctuate over time, planners may have to enhance the order release decision in order to avoid costs of changing the total available capacity. Our study reveals that the quality of the order release decision is the key to an improved capacity balance over the periods.

In order to develop solution approaches for this multi-product multi-stage problem, we used insights from mixed-model assembly line sequencing algorithms and workload control literature. Four heuristics and a We tested the five solution approaches in a rolling schedule. This enabled us to take into account the consequences of the former sequence decisions of the approaches for the new cycle. We evaluate the average total capacity shortage per cycle and the frequency of shortages for the various solution approaches.

Our experimental design evaluates the performance of the approaches for two levels of variation of total capacity requirements per order and for two levels of variation of the distribution of the workload over the stages. Moreover, we evaluated the effect of changing the length of the planning horizon and the number of stages. Surprisingly, the simple FillCap heuristic that selects an order that consumes as much capacity in the first stage of its release as possible performs in all experiments better than the more sophisticated capacity balancing heuristics. This holds true even if the number of stages m increases. We expect that the main reasons are to be found in the bad balance at the end of the cycle, as the more sophisticated heuristics do aim at a very good balance at the start of the cycle, without taking into consideration the effects of their choices at the end of the cycle. However, this study has not examined the main reasons for the bad performance of the sophisticated heuristics, as it expected them to perform better. Future research should elaborate on this. The performance of the heuristics is very sensitive to an increase in the variation of the distribution of workload over the stages. Increased variation of the total capacity requirements of an order has only a marginal impact on performance. The use of the mathematical model instead of one of the heuristics results in an almost total elimination of shortages in our experiments. Shortage frequencies of at least 30-60 percent were avoidable by using the mathematical model. The time needed for finding an optimal solution is very short for the problems we have solved (up to 15 orders and 10 stages). The size of problems that we have investigated is realistic for real life manufacturing systems, and implementation of the mathematical optimization model is easy to accomplish. We conclude therefore that the use of such a solution approach should be considered, as it strongly improves the capacity balance in synchronous manufacturing systems. Future research should verify if modifications of the proposed heuristics for synchronous manufacturing lead to performance improvements. We suggest to develop and test heuristics that take into account uncertainty with respect to the work content and available capacity. Genetic algorithms can be applied as well. The current study has applied deterministic optimization in a rolling schedule horizon. We think that the use of a rolling schedule has important benefits when testing the performance of solution approaches and should be applied to other problems as well. Step A i U C Available

F

= = ∀ = ∀ = - = = + = - = = ∈ ∧ = ≠ ∅ ≤ = - ∑ { }
Step IF

m t m ij t j t i it t j j ij A Select i A ELSE Select i U LoadAimedAt t ARC ALoad such that i C LoadAimedAt i i Available C Step X Y C j m ALoad ALo - = + - ≠ ∅ ∈ ∈  = + ⋅ -   = -    -  = = ∀ = = ∑ { } 1 :
1 . Step A i U C Available

Step IF A Selec

m ij tj j it j j ij t i A ELSE Select i U i C LoadAimedAt Step X Aload Aload C j m U U i IF U Goto Step ELSE Stop = ∈ ∈ = - = = + ∀ = = - ≠ ∅ ∑ F o r P e e r
+ = ∈   = = ∈     ≤     { } ( ) [ ] f set 3 Select randomly stage : min , 1, 1
Maximum variation of remaining volume to be allocated to stage j Select randomly workload ,

ij X j Um MV MixVar AV VR AV Um MV C AV MV AV MV                               ∈ = - - - + = ∈ - + ( ) { } 1
B I C A 0 2 2 2 2 J D H F 0 4 3 1 3 H E I B 3 0 4 2 4 A A B E 3 0 -4 3 5 C G E C 2 2 1 1 6 F B A H 5 3 2 0 7 I C G J 3 -1 1 0 8 D J J D 3 2 0 0 9 E H F I -6 4 0 0 10 G F D G 0 -1 8

  Order Sequencing and Capacity Balancing in Synchronous ManufacturingJAN RIEZEBOS * Department of Operations, Faculty of Economics and Business, University of Groningen, The Netherlands Introduction

  0.7 seconds CPU time. The use of this version of Lingo in the rolling schedule experimental design did not allow us to solve problems with 25 n m + > .

  developed to solve the capacity balancing problem in a synchronous manufacturing system.

Figure 2 .

 2 Figure 2. Performance for increased variation in distribution of workload over stages

Table 1

 1

			results in four periods that encounter a capacity shortage: t=2,6,9,10. Can a
	better order sequence be found?
	2.2	Mathematical problem formulation
	Let	i=1,…,n	index for orders
		j=1,…,m	index for stages
		t=1,…,n+m-1 index for periods
	Parameters
	ij C	Capacity requirements to complete stage j of order i
		i=1,…,n; j=1,…,m
	tj CR	Capacity requirements to complete stage j in period t for an order from a former cycle
		t=1,…,m-1; j=t+1,…,m
	j ARC Average required capacity in stage j =	∑	1 1 -= j t	1 ∑ + -n j tj CR +	1 = n i	ij C
		j=1,…,m-1
	t AC Available capacity in period t (assuming the capacity is fully cross-trained)
		t=1,…,n+m-1

an overview of the variables and parameters in terms of the structure of Table 1. Note that the value of the variable tj

												tj CR for orders that have already started but are not yet completed;
	• available capacity per period	t AC ,
	determine	X	it	(	i	=	1,..., ; 1,..., n t =	n	)	(the sequence of the n orders)
	such that	∑	1 + -1 n m t =	t w CS	t	is minimized.
	**INSERT FIGURE 1 ABOUT HERE***
	Figure 1 provides Y in this table is area-specific.
	• In the lower-left side of the table, tj Y is determined by the given capacity requirements	tj CR of already
	started but not yet completed orders.
	• In the upper-right side of the table, it is estimated by calculating the average required capacity in the
	stage.
	• In the remaining part of the table, it is calculated as a linear function of the order sequence decision and
	the known capacity requirement of the orders. We use the following expression for calculating this stage
	load:
												t j Y	1,	j	n i	1	it X C ij	t	1,...,	n j	1,...,	m

  Table 3 shows the full factorial experimental design.

*** INSERT TABLE 3 ABOUT HERE*** Each of the configurations (experiments) is replicated 100 times with a run length (rolling schedule) of 50 cycles.

Table 1 .

 1 Order sequencing with 10 products a week

	Page 21 of 28	International Journal of Production Research
	day	Mon	Tue	Wed		Thu		Fri		Mon2	Tue2
	bucket (4 hours)	am pm am pm am pm am pm am pm am pm am pm
	period t	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	Stage \ Order	A	B	C	D	E	F	G	H	I	J
	j=1	3	5	3	2	2	3	2	4	3	6	3.3 3.3 3.3 3.3
	j=2	4	5	3	2	6	2	2	2	4	3	2	3.2 3.2 3.2
	j=3	6	4	4	4	2	6	5	2	5	4	5	2	4.1 4.1
	j=4	3	4	5	6	4	8	3	4	8	4	4	5	2	4.6
	j=5	2	3	2	4	2	4	5	2	4	5	4	4	3	2
	Total	18 21 17	18 16 23	17 14 24	22 21 22	21 28
	(Exp.) Shortage	0	1	0	0	0	3	0	0	4	2	0	0	0	0

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.uk

Table 2 .

 2 Comparison of the solution approaches

			Sequence			Unused capacity in period t
	t	FillCap	AvgLoad	(Avail-) StageLoad	Optimal	FillCap	AvgLoad	(Avail-) StageLoad	Optimal
	1

Table 3 .

 3 Full factorial design

	3

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.uk

Table 4 .

 4 ANOVA results

	Shortage	Frequency

Table 5 .

 5 Multiple comparisons of performance solution approaches

	95% Confidence Interval

Table 6 .

 6 Performance of solution approaches .08 .09 .36 .22 .00 2.18 2.26 2.18 3.01 .00 ± 1 4.15 5.44 11.84 6.83 .00 .59 .70 .98 .75 .00 7.08 7.81 12.04 9.15 .00 5 ± 2 ± 3 4.72 7.36 12.15 7.47 .00 .60 .77 .98 .74 .00 7.85 9.62 12.45 10.05 .00 ± 1 .83 1.04 2.03 1.29 .00 .29 .34 .66 .39 .00 2.89 3.07 3.07 3.32 .00 ± 1 ± 3 .96 1.25 2.02 1.50 .00 .31 .37 .64 .39 .00 3.07 3.37 3.15 3.78 .00 ± 1 3.53 4.13 6.64 4.97 .00 .64 .69 .93 .74 .00 5.54 5.97 7.12 6.74 .00 10 10 ± 2 ± 3 4.15 5.34 7.19 5.91 .00 .64 .72 .93 .74 .00 6.53 7.40 7.77 7.98 .00 .12 1.12 .00 .09 .08 .47 .33 .00 2.41 2.15 2.37 3.44 .00 ± 1 5.43 6.98 17.86 8.71 .00 .68 .77 1.00 .80 .00 7.96 9.11 17.90 10.88 .00 5 ± 2 ± 3 6.07 9.70 18.59 10.04 .00 .70 .84 1.00 .81 .00 8.70 11.61 18.66 12.36 .00 Figure 1. Variables, parameters and structure of Table 1

							Shortage				Frequency			Exp. Shortage
	n	m	MIXVAR	VOLVAR	FillCap	AvgLoad	Stageload	AvailStageLoad	Optimal	FillCap	AvgLoad	Stageload	AvailStageLoad	Optimal	FillCap	AvgLoad	Stageload	AvailStageLoad	Optimal
	15	10	± 1 ± 1 ± 1 ± 2	± 1 ± 3 .67 .00 ± 1 .05 .07 .45 .12 .00 .03 .04 .26 .07 .00 1.39 1.56 1.75 1.67 .00 .19 .20 .79 .05 .08 .74 .13 .00 .03 .04 .39 .07 .00 1.33 1.50 1.89 1.69 .00 ± 3 .23 .18 1± 1 1.25 1.37 3.06 1.72 .00 .39 .43 .82 .47 .00 3.21 3.21 3.73 3.65 .00 ± 3 1.29 1.57 3.05 2.21 .00 .38 .43 .78 .49 .00 3.42 3.64 3.93 4.46 .00 ± 1 5.12 5.73 10.25 7.05 .00 .76 .81 .99 .83 .00 6.78 7.10 10.37 8.50 .00 ± 3 6.16 7.79 11.28 8.60 .00 .78 .84 .98 .84 .00 7.86 9.25 11.49 10.25 .00

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research

Acknowledgements

We like to express our thanks to Professor G.A. Süer, University of Ohio, for providing us many details on the jewellery firm and stimulating discussions.

Appendix

FillCap heuristic:


Sibt Ul Hussain
email: sibt.ul.hussain@gmail.com

Bill Triggs
email: bill.triggs@imag.fr

Feature Sets and Dimensionality Reduction for Visual Object Detection

We describe a family of object detectors that provides state-of-the-art error rates on several important datasets including INRIA people and PASCAL VOC'06 and VOC'07. The method builds on a number of recent advances. It uses the Latent SVM learning framework and a rich visual feature set that incorporates Histogram of Oriented Gradient, Local Binary Pattern and Local Ternary Pattern descriptors. Partial Least Squares dimensionality reduction is included to speed the training of the basic classifier with no loss of accuracy, and to allow a two-stage quadratic classifier that further improves the results. We evaluate our methods and compare them to other recent ones on several datasets. Our basic root detectors outperform the single component part-based ones of Felzenszwalb et. al on 9 of 10 classes of VOC'06 (12% increase in Mean Average Precision) and 11 of 20 classes of VOC'07 (7% increase in MAP). On the INRIA Person dataset, they increase the Average Precision by 12% relative to Dalal & Triggs.

Introduction

Despite the substantial advances made during the past decade, the detection of visual object classes in images remains a challenging problem that receives a great deal of attention in the vision community [START_REF] Everingham | The PASCAL Visual Object Classes Challenge Results[END_REF]. Although generative models have considerable potential for deep image understanding, the best current object detectors are trained discriminatively, typically taking the 'sliding window' approach in which a detection window is swept across the image at multiple positions and scales, and a window-level object / non-object classifier is evaluated at each window position. We use this approach and assume that it is familiar [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF].

Typical window-based detectors can be divided into two stages. First, image processing is used to extract a set of robust visual descriptors that implicitly contains the information needed to make object / non-object decisions while resisting extraneous effects such as changing object appearance, pose, illumination and background clutter. Secondly, a machine learning based classifier uses the descriptors to make window-level object presence decisions, often followed by postprocessing to merge nearby decisions. The classifiers are typically trained using large sets of labelled training examples. The overall performance depends critically on all three elements: the feature set, the classifier & learning method, and the training set.

In this work, we present a family of detectors that give state-of-the-art results for human and object class detection on several important datasets. The detectors combine several recent advances including a rich and complimentary set of visual features [START_REF] Ahonen | Face description with local binary patterns: Application to face recognition[END_REF][START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF][START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF], efficient dimensionality reduction [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF], and latent training with parts [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF].

Related Work. The literature on sliding window based human and object detectors is vast.

Here we mention only a few relevant methods [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF][START_REF] Schwartz | Human detection using partial least squares analysis[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF][START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF]. Dalal & Triggs [2] developed Histogram of Oriented Gradient (HOG) features for human and object detection. Felzenszwalb et al. [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] built a sophisticated multi-component part-based object detection framework over Latent SVM and HOG. Vedaldi et al. [START_REF] Vedaldi | Multiple kernels for object detection[END_REF] used multiple kernel learning to combine six feature sets (including bag-of-words, dense visual words, self-similarity descriptors and edge based descriptors) in a spatial pyramid framework for object detection. Schwartz et al. [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF] combined HOG with color histograms and texture co-occurrence features in a QDA based human detector. Wang et al. [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF] used HOG and Local Binary Patterns (LBP) with partial occlusion handling for human detection.

Contributions. Our work builds on the insights and methods of several of the above approaches. It makes two main contributions: (i) we show that an extended feature set incorporating Histograms of Oriented Gradients (HOG), Local Binary Patterns (LBP) and Local Ternary Patterns (LTP) gives state of the art performance on several important datasets; (ii) we show that Partial Least Squares dimensionality reduction can be used to further enhance this in several ways including faster training, improved linear detectors and efficient nonlinear ones. We use the Latent SVM learning framework [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. For simplicity we focus mainly on single component linear SVM based root detectors, although some results are also presented for multiple component and part based detectors.

Feature Sets

Object detectors are critically dependent on the visual features that they use, which must capture the information needed to identify objects of the class despite highly variable object appearance, pose, lighting, clutter, background texture, etc. Advances in feature sets have been a constant source of progress over the past decade. Our detector owes much of its accuracy to the use of a combination of three recent high-dimensional feature sets: Histograms of Oriented Gradients (HOG); Local Binary Patterns (LBP); and Local Ternary Patterns (LTP). Each of these is strong in its own right, and together they turn out to complement one another, leading to exceptionally good performance.

Histograms of Oriented Gradients (HOG)

. HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] is one of the most successful recent feature sets for sliding window based visual recognition. Inspired by the features used by SIFT interest points, it is computed by spatially pooling oriented image gradient strengths into a grid of overlapping cells, with careful attention to normalization. It captures mainly coarse shape (object contour) information, with very strong resistance to illumination variations and some robustness to small spatial variations.

Our implementation of HOG is similar to [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. We use a simple grid of 8×8 pixel cells with 9 bins of unsigned gradient orientation over color images. Each cell is grouped into four 2×2 cell blocks for SIFT-style normalization, giving 36 feature dimensions per cell. Reducing to 9-D per cell (normalization by the average of the 4 neighbouring blocks) increases the miss rate on the INRIA test set at 10 -5 False Positive Per Window (FPPW) from 20% to 23%, while reducing to 13-D as in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] by summing over the 4 normalization and the 9 orientation channels increases it to 22%. Although these performance losses are small given the reduction in feature vector size, we achieve a similar effect with our PLS projection scheme without suppressing any information.

Local Binary Patterns (LBP). LBP features capture microscopic local image texture. They have proven very successful for texture classification and face recognition [START_REF] Ahonen | Face description with local binary patterns: Application to face recognition[END_REF][START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF][START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF], and they have recently been used for human detection [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF]. LBP descriptors are built by converting each pixel to an 8 bit binary code by thresholding the 8 surrounding pixels at the value of the central pixel, then histogramming the resulting codes over a spatial pooling region, typically one cell of a local grid covering the detection window. Common refinements include using a circle of 8 surrounding pixels rather than a square, with pixel values obtained by interpolation, and histogramming uniform patterns rather than full 8-bit ones. A pattern is 'uniform' if it contains at most one contiguous group of 1's within the 8 pixel circle. In practice the vast majority of pixels generate uniform patterns. Uniform LBP histograms have 59 bins, one each for the 58 possible uniform patterns and one for all of the nonuniform ones.

Our detector uses uniform LBP codes based on circles of radius 1 pixel, pooled into 8×8 pixel cells, c.f . [START_REF] Ahonen | Face description with local binary patterns: Application to face recognition[END_REF][START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF]. LBP codes are computed separately on the R, G and B color channels then pooled into the same histogram. For the best performance1 , the resulting histograms are normalized to sum 1 then square-rooted ("L1Sqrt" normalization). Using L2 instead of L1Sqrt normalization increases the miss rate on INRIA from 30% to 38% at 10 -5 FPPW.

Local Ternary Patterns. LTP is a simple generalization of LBP introduced by [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. It uses the same sampling structure as LBP but instead of making binary pixel comparisons it makes 3-way ones depending on whether the pixel is above, within a threshold τ of, or below the central pixel. For simplicity the resulting 8-digit ternary codes are split into 'above' and 'below' binary codes, which are separately histogrammed as uniform LBP patterns as in [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. The introduction of τ breaks the monotonic illumination invariance of the descriptor, but it helps to suppress the noise that dominates LBP responses in near-uniform regions and it provides an additional parameter that can be tuned to extract complementary information. Empirically, a threshold of τ = 5 gray-levels (out of 255) gave the best performance. Thresholds between 3 and 10 give very similar results, while larger ones tend to discard too much texture information and smaller ones give descriptors that are too strongly correlated with LBP for complementary. As Fig. 1 and the experiments below show, the LBP and τ = 5 LTP responses have rather different characters, with LBP capturing mainly dense local texture and LTP putting more emphasis on strong textures and object contours. Although still a local texture descriptor, LTP provides relatively complementary information to LBP.

The datasets tested here have only a limited range of illumination variations and we found that preprocessing the images using the method of [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF] did not enhance the performance. More precisely, adding gamma correction reduced the miss rate at 10 -5 FPPW for LBP alone from 28% to 20%, but it did not improve the performance of combinations including both LBP and LTP. Adding DoG filtering reduced the performance.

Results. Fig. 2 shows results for various combinations of these feature sets, for windowlevel classifiers on the INRIA test set and for complete root detectors on the VOC'06 Person test set. The window-level classifiers were trained and evaluated using the method of [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], i.e. traditional linear SVM trained on cropped positive and negative windows with several iterations of search for hard negatives, followed by a window-level scan over the test set to evaluate a DET curve (lower curves are better). The complete root detectors were trained and evaluated using the method of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], i.e. with linear Latent SVM learning, scale-space merging of overlapping detections, and evaluation based on Precision-Recall curves and Average Precision / Area Under Curve. Combinations of features give the best results in all cases, with HOG+LBP+LTP being best in all but the middle plot, where it came second. There is no clear winner between HOG+LBP, HOG+LTP and LBP+LTP, but all perform well and LBP and LTP are quite complementary 2 . As far as we know, the results of the window-level classifier on the INRIA dataset are the best reported so far.

Despite fig. 2 (left) and (middle), an LBP/LTP block size of 8×8 gives better performance than 16×16 for the complete root detector. It increases the Average Precision from 29.1% to 32.8% on the VOC'06 Person test set and by 80.1% to 81.6% on the INRIA Person test set. When used in combination with HOG, the LBP/LTP block normalization schemes L1Sqrt and L2 give similar results -respectively 32.8% and 33.5% AP on VOC'06 person and 81.4% and 81.6% AP on INRIA Person -but when LBP is used alone, L1Sqrt normalization is preferred. Provided that some normalization method is used, the relative weighting of the HOG, LBP and LTP sections of the feature vector has little impact on the performance of final detector. For HOG+LBP+LTP, replacing color descriptors with grayscale ones increases the miss rate at 10 -5 FPPW on the INRIA test set from 4.8% to 6.5%.

Classifiers

We use sliding window based detectors over high-dimensional feature sets, with SVM classifiers trained using the Latent SVM approach of Felzenszwalb et al. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] and incorporating multiple stages of search for hard negatives as in [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. Multiple root detectors and parts can be incorporated along the lines of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. Most of our classifiers are linear, but we also test some quadratic ones based on Partial Least Squares (PLS) dimensionality reduction. Moreover, we show that our classifiers can be sparsified with negligible loss of precision.

Latent SVM. Latent SVM training [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] refines the training examples by running a local search around their labelled image positions and scales, iteratively finding the best match against the current classifier estimate and then retraining the classifier using the resulting matches. This provides cleaner training data and, by mimicking the way in which the classifier will actually be used in practice, it often significantly improves its performance, particularly for classes with highly variable spatial layout. For example on the INRIA dataset, Latent SVM learning increases the average precision from 75% to 79% for HOG features and from 77% to 80% for HOG+LBP+LTP features.

Dimensionality Reduction using Partial Least Squares (PLS). We use very high dimensional feature vectors (20448 dimensions for our full feature set over 48×128 windows). These are bulky to store and slow to process during training, and despite the use of linear SVM classifiers there is always a risk of overfitting. One way to handle this is to introduce some form of dimensionality reduction as a preprocessing stage before learning. Here we use Partial Least Squares (PLS), c.f . [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF].

PLS is an iterative algorithm for building low-dimensional orthogonal projections that have good predictive power in a given regression task (here, linear classification). It was developed in chemometrics where it is used to produce linear predictors in situations with few observed examples and many highly-correlated variables [START_REF] Wold | Pls-regression: a basic tool of chemometrics[END_REF]. Formally, it finds a linear regressor of the form Y = X B + E by a low-dimensional projection T = X W followed by regression Y = T Q + E, so that B = W Q. Here, X and Y are input and target matrices with each row representing one example, W is the orthogonal projector, Q the corresponding regressor, and E is the residual error matrix. The algorithm scales the variables in X and Y to zero mean and unit variance, then iteratively evaluates the best new column that can be added to the current W and Q to minimize the prediction (regression) error, and adds this.

In the context of our detector, in each training iteration, after Latent SVM alignment, we use PLS of feature vectors against class labels to project out a discriminative subspace of feature space for SVM training. Both linear and nonlinear classifiers can be trained in the reduced space. PLS is useful even for linear ones. Even including the cost of PLS learning and reduction, it speeds up batch SVM training by a factor of 10-15 or more, e.g. reducing training times from 10-15 minutes per stage to 30-90 seconds per stage in the last stages of the full detector. In our experiments it leads to little or no loss of accuracy. Indeed, it often slightly increases the accuracy 3 . The resulting (linear) classifier f can be pulled back through the PLS projection W to give an equivalent classifier W f on the original feature space: this can be run more efficiently than f because it does not require test examples to be projected through W. By default we use 30-D PLS projection when training linear classifiers, but other values give similar results.

Type of Classifier. Our baseline classifier is (latent) linear SVM trained using SVMLight [START_REF] Joachims | Making large-scale svm learning practical. advances in kernel methodssupport vector learning[END_REF], but we also tested a number of other linear and nonlinear classifiers. We tried several variants of L1 and L2 linear Logistic Regression, but none of them outperformed linear SVM. For example L2 Logistic Regression trained using LibLinear ('L2LR') gave AP on VOC'06 Person of 30%, as compared to 33% for linear SVM. For conventional kernel SVMs, the training and testing times are often too high to permit large scale experiments. Instead we tested two forms of embedded quadratic classifier that can be run efficiently.

The first approach is inspired by the fact that Intersection Kernel SVM (IKSVM) can be viewed as a method for learning a nonlinear function f i (x i ) for each feature dimension i such that ∑ i f i (x i ) is a good classifier. This can be achieved more directly by expanding each f i (x) in terms of some convenient set of basis functions b i j (x) such as polynomials, and learning the resulting basis coefficients using a standard linear SVM over the features {b i j (x i )}. Our 'CoordinateQuad' method does just this, with features x i , x 2 i . In practice we find that it gives identical accuracy to IKSVM (and only slightly better accuracy than simple linear SVM) in about 2.4 seconds per image, which is much faster than FastIKSVM [START_REF] Maji | Classification using intersection kernel support vector machines is efficient[END_REF]. Moreover, the learned x 2 i coefficients turn out to be very small so there is little evidence that the noisy and highly nonlinear 1D functions learned by IKSVM are actually needed for good classification. Adding higher powers of x i gives little further improvement. In general, for the feature sets commonly used in visual object recognition, we remain sceptical of the advantages of IKSVM relative to simple feature set expansions of the kind suggested above.

Our second quadratic classifier, 'FullQuad', is a full quadratic SVM in the PLS-projected feature space, i.e. it is a linear SVM over a feature set containing the projected features and all bilinear products of them [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF]. This is feasible because PLS projections are highly discriminant even with quite small numbers of dimensions (here, 14). The relative weighting of the linear and quadratic components of the feature vector has some effect on performance, but for good performance we found that it sufficed to normalize the range of each to unity.

Table 1 summarizes the performance of various nonlinear classifiers on the VOC'06 person class. The full quadratic classifier in the reduced space has the best overall accuracy but it is rather slow, requiring about 5 seconds per image because each test window must be projected to the reduced feature space. We can reduce this to about 1.7 seconds per image by using a two stage cascade, training a linear SVM on the final stage training set of the quadratic classifier to remove as many negatives as possible while keeping 95% of the positives, and using this as a prefilter before the PLS projection ('FullQuadCascade'). The converse approach -learning a PLS based quadratic classifier as a postfilter on the hard negatives of a linear SVM -also works but it is less accurate.

In general, on these datasets we find that nonlinear methods are slightly more accurate than the linear ones but that the differences are small. In particular, the challenging 'hard negatives' found in the later stages of detector training do not appear to have systematic properties that yield easily to the nonlinearities tested here.

Sparsity.

In our experiments, if the learned SVM weight vectors are examined, many of their components are small. The smallest 50% of the components typically carry only about 20% of the total weight. This is to be expected because most visual classes are characterized by relatively sparse cues such as outlines or particular types of textures. To the extent that the small components represent noise inherited from the training set, it can be useful to suppress them. We are currently working on an efficient L1 regularized hinge-loss SVM method for this (existing algorithms that we tested proved too inefficient for problems of this size), but in the mean time a similar effect can be achieved by taking the trained linear SVM, deleting the features whose SVM weights have small absolute values, and optionally retraining the SVM over these features alone. Such retraining helps. For VOC'06 People, it gives almost identical performance to the original detector (34% AP) with 49% of the features active, and 32% AP with 30% active. Similarly, an L1 regularized L2 SVM gave 31% AP with 14% of the features active and L1 logistic regression gave 29% AP with 24% active. Further work is needed here. Part Detector. Our part-based detectors are represented and trained in almost the same way as [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], using 2× finer features and locally quadratic penalties on their displacements. We select initial part regions by greedily maximizing the sum of the positive SVM weights of the learned root detector within the region, then initialize the part detectors by densely interpolating the root weights. For the PLS based approaches, we learn separate PLS reductions for each part and for the root at each round of training, appending the (unreduced) deformation costs to these to make the complete reduced feature vector. Unlike [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], we limit the range of possible part displacements by truncating the quadratic displacement penalties. We find that this makes part learning and detection significantly more reliable. Further Implementation Details. For all of the classes reported here, we force the root detector to be left-right mirror symmetric, and force the parts to come in pairs that are mirror images of one another with mirror image displacement penalties. This allows us to reduce the effective feature dimensions during training by a factor of 2. The transformations are implemented using look-up tables that map HOG components and LBP/LTP codes to their mirror images. We used the densified version of SVMLight [START_REF] Joachims | Making large-scale svm learning practical. advances in kernel methodssupport vector learning[END_REF] to train linear SVM's. We tried several more recent SVM packages including LibLinear, but SVMLight proved to be the most reliable. When training Latent SVM root detectors, we pre-calculate and cache the features of the (typically 10-14) detection windows with more than 70% overlap with the original annotation boxes in position and scale, as this saves a good deal of computation by avoiding the need to recompute the local scale-space pyramids. Moreover, for each positive example in Latent SVM, we select the k > 1 best detection windows near the example for use in SVM training, not just the single best window. For k ≤ 3 this gives the same final performance while allowing the number of training iterations to be reduced by a factor of nearly k. It also compensates to some extent for the imbalanced ratio of hard negatives to positives in the training set. Taking k ≥ 4 progressively reduces the accuracy.

Experiments

We compared our methods with the root and part-based detectors of Felzenszwalb et al. [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] and the extended feature set approaches of Schwartz et al. and Wang et al. [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF][START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF] on various standard datasets including PASCAL VOC'06 and VOC'07 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge Results[END_REF], INRIA People [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] and ETHZ [START_REF] Ess | Depth and appearance for mobile scene analysis[END_REF]. In this section, unless otherwise noted, the root detectors are trained using linear Latent SVM over PLS reduced features, the HOG and LBP/LTP features are computed over 8×8 pixel cells, L2-hysteresis normalization is used for HOG and L1Sqrt normalization is used for LBP/LTP, and no image preprocessing is done before feature extraction. For the part based approaches we report variants trained using PLS features and unreduced features. We use the standard evaluation protocols, e.g. for VOC'06 and VOC'07 we score by Average Precision (AP) on the test set. Fig. 3 summarizes some of the results for three classes from the INRIA and VOC'06 datasets. VOC'06. We performed our most detailed experiments on VOC'06, using the training and validation sets for training. Table 2 summarizes the results from several of our (rows 1-7) and 1Root (0.24) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] 1Root+Parts (0.34) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] 2Root+Parts (0.38) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0. [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] improves the accuracy. Rows 4-5 show that the PLS based parts detectors have performance similar to, but slightly lower than, the corresponding non-PLS ones. Rows 8-10 show that our single-component object detectors give better results than the multiple-component ones of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], the previous best performers on this dataset. The improvement is largely due to the high precision of our PLS-based root detectors. Indeed, these outperform the part-based methods of [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] on 9 of the 10 classes4 . On VOC'06, with our single threaded implementation on a 2.6 GHz P4 workstation, our root person detector runs in about 1.4 seconds per image. VOC'07. Table 3 gives the results of our detectors on various VOC'07 classes ( [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF] represent the state of the art). Our root detector (row 1) already outperforms the part based detector of [START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] (row 5) on 11 of the 20 classes, and adding an additional root (row 2) or parts (row 3) further improves the results in most cases. Row 4 shows that solely HOG based parts detectors lead to the best overall performance (slightly better than complete feature sets based part detectors). Nevertheless, the erratic results for some of the classes (Bird, Cat) suggest that the heuristics used to initialize multiple roots and parts could still be improved.

INRIA Person.

As in [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], we evaluate window-level classifiers using Detection Error Tradeoff (DET) curves and complete detectors using Precision-Recall curves and Average Precision (AP) scores. Fig. 2 (left) shows the performance of the window-level root classifier: 4.7% miss rate at 10 -5 FPPW, compared to 5.8% for [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF] and 5.6% for [START_REF] Wang | An hog-lbp human detector with partial occlusion handling[END_REF]. Fig. 3 (left) shows the corresponding Precision-Recall curves with an AP of 84.1% for our two stage linear-quadratic root classifier and 82% for our linear root one. (The best known AP on this dataset is 86.9% for the part-based approach of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]). Our root detector runs in about 2.7 seconds/image on INRIA.

ETHZ. For comparison with other methods on this dataset, we plot Recall vs. False Positives Per Image (FPPI). Fig. 4 presents results for our linear root detectors trained on the INRIA and VOC'06 Person sets and tested on three ETHZ sequences. Our methods outperform the complex approach of [START_REF] Ess | Depth and appearance for mobile scene analysis[END_REF][START_REF] Ess | A mobile vision system for robust multi-person tracking[END_REF] and, despite being linear and having a 40× lower feature dimension, they have higher recall at low FPPI than the QDA based method of [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF] on Sequence 1 and near-identical performance on the other sequences. This allows them to process an image every 3 seconds, whereas [START_REF] Schwartz | Human detection using partial least squares analysis[END_REF] takes 120 (or 60 for the 2 stage method).

Discussion

We have presented a family of sliding window object detectors that combine a rich visual feature set (Histogram of Oriented Gradient, Local Binary Pattern and Local Ternary Pattern features) with Latent SVM training and Partial Least Squares dimensionality reduction to give state of the art performance on several important datasets including PASCAL VOC'06 and '07, INRIA People and ETHZ. The main findings are as follows. (i) HOG, LBP and LTP are strong feature sets in their own right, but they capture somewhat complementary information so combinations of them are even stronger, with HOG+LBP+LTP being strongest of all and much stronger than HOG alone. The complementarity of LBP and (with a suitable threshold) LTP was perhaps not evident a priori. (ii) As others have confirmed, the framework of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] with root+parts detectors and Latent SVM training is very effective. (iii) PLS dimensionality reduction is a useful tool that can both speed linear SVM training with little loss (and perhaps even a small gain) in accuracy, and allow efficient nonlinear classifiers. In contrast, we are sceptical of the benefits of IKSVM relative to simple feature embeddings.

(iv) Even using rather naive methods, the feature set can be further sparsified by a factor of 2-3 with little loss of accuracy. Future work. We are working on improved large-scale L1 regularized SVM algorithms for enforcing sparsity and on including spatio-temporal features into our detectors. The batchmode algorithms that we use to calculate PLS bases are inconvenient for very large feature sets and on-line algorithms would be desirable.

Figure 1 :

 1 Figure 1: Different feature channels, from left to right: (a) original image; (b) HOG image; (c) color LBP image; (d) & (e) positive & negative color LTP images.

Figure 2 :

 2 Figure 2: Performance of various combinations of features. DET curves on the INRIA test set for (left) LBP/LTP block size 16×16, (middle) LBP/LTP block size 8×8. (right) Precision-Recall on the VOC'06 Person class for LBP/LTP block size 8×8.

Figure 3 :

 3 Figure 3: Precision-Recall of several root and part detectors on three datasets: (left) INRIA Person; (middle) VOC'06 Person; (right) VOC'06 Car.

Figure 4 :

 4 Figure 4: Performance on the ETHZ test set for our linear SVM root detectors trained on the VOC'06 and INRIA sets, versus some competing methods: (left) Sequence 1 (999 images); (middle) Sequence 2 (450 images); (right) Sequence 3 (354 images).

Table 1 :

 1 Performance of various nonlinear classifiers on the VOC'06 Person class.

	Method	Linear FastIKSVM CoordinateQuad FullQuad FullQuadCascade L2LR
	Space	PLS	Full	Full	PLS	PLS	Full
	Avg.Prec	33	35	34	35	35	30
	Run Time (sec) 1.4	74	2.4	5	1.7	2.7

Table 2 :

 2 Average Precision for some of our detectors and[START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] on VOC'06.

	Class	Mean	Aero	Bike	Bird	Boat	Bottle	Bus	Car	Cat	Chair	Cow	Table	Dog	Horse	Mbike	Person	Plant	Sheep	Sofa	Train	TV
	1 Root	22.8 25.7 39.8 9.2 6.3 23.6 33.2 37.3 12.6 10.6 17.3 25.7 9.6 35.5 35.4 14.2 13.1 16.6 24.6 27.0 38.0
	2 Roots	23.0 25.9 43.6 1.0 11.7 20.4 32.7 43.2 3.9 13.6 18.7 18.3 5.2 43.5 37.7 25.1 10.4 19.7 22.8 24.4 38.7
	1 Root+Parts 25.6 27.5 42.4 10.1 5.6 27.5 37.5 47.4 18.8 12.1 19.9 23.1 15.8 36.4 38.7 14.8 15.7 20.8 25.0 32.0 41.4
	HOGParts 26.0 28.3 43.3 2.9 4.9 29.1 36.2 44.8 15.7 14.3 20.4 28.5 14.5 43.6 39.4 26.7 16.1 21.2 26.4 23.3 40.1
	Root+Parts[6] 21.3 18.0 41.1 9.2 9.8 24.9 34.9 39.6 11.0 15.5 16.5 11.0 6.2 30.1 33.7 26.7 14.0 14.1 15.6 20.6 33.6

Table 3 :

 3 Average Precision for some of our detectors and[START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] on VOC'07.

	Felzenszwalb et al.'s (rows 8-10) detectors. Rows 1-3 show that progressively adding parts
	and bounding box prediction

Using squares instead of circles reduces the performance. Using a larger radius improves it slightly on some problems but reduces it on others. Histogramming each color channel separately sometimes increases it but not enough for us to recommend it as a general practice given the increase in feature vector size.

Here, the LTP threshold was tuned to optimize the combination HOG+LBP+LTP. This is not necessarily the best setting when using LTP alone or with just one other feature set.

SVM detectors are based on limited numbers of noisy support vectors, for example training examples with background clutter. PLS dimensionality reduction implicitly averages over many examples. Presumably, this sometimes projects away part of the noise and hence reduces overfitting.

Several variants of[START_REF] Felzenszwalb | A discriminatively trained, multiscale, deformable part model[END_REF] are available on their website. Here we use their basic method as it is the one whose training algorithm is most similar to ours.

Work supported by the Higher Education Commission (HEC) of Pakistan and European research project CLASS.