J Mendoza

G Mejia

A SPREADSHEET BASED SCHEDULING SYSTEM FOR A SMALL PRINTING COMPANY

Keywords: Scheduling, Flexible Job Shop, Simulated Annealing, Decision Support Systems

This work presents the design and implementation of a low cost scheduling tool based on Microsoft Excel, designed for a small printing company in Colombia. The company scheduling problem can be defined as a Flexible Job Shop with highly sequence dependent set up times where makespan is the objective function in a weekly planning horizon. The system architecture includes a product specifications data base, an engine which transforms the product specifications into shop floor operations, a processing times data base and a graphical user interface. The proposed scheduling tool uses Simulated Annealing (SA) for optimization purposes. An initial schedule is generated by a non-delay schedule generation algorithm combined with dispatching rules. Insertion moves on each machine were used for the generation of neighbors. The cooling schedule for the implemented SA algorithm is also well explained. In terms of the operation management the results benefit the company with reduction from hours to seconds on the time required to build a feasible schedule and the availability of new tools to generate reports of shop floor performance metrics. In terms of makespan the results suggest improvements of 40%.

MOTIVATION

Paper and cardboard industry accounts for the 4.4% of Colombian manufacturing. Annually more than 250 enterprises in this sector are responsible for over 1900 million dollar contribution to the total manufacturing production [1]. Historically manufacturing in Colombia is based on medium and small size enterprises (PYMES for its acronym in Spanish) which represent more than 96% of the total number of companies established in the country [1]. According to the 2005 PYMES survey [START_REF]of Colombia[END_REF], 65% of these companies are interested on investing on information technology solutions (TICS), but only 13% of Colombian PYMES have done it in the last years. The main reasons for this situation are the high cost of buying and implementing this type of technologies and the constrained investment capacity of PYMES. This work presents the implementation of the scheduling module of a low cost production planning system based on spreadsheets, developed for a small printing company in Colombia. The main goal of this work is to provide the company with a tool to help planning its operations and to improve its productivity. The socialization of this experience pretends to encourage other researchers and companies to develop similar tools to help PYMES to grow and to keep accomplishing their important role in emerging economies.

1.1 Background Impresos y Empaques D-Cartón Ltda is a small company, specialized in the production of cardboard packing products. The company serves more than 50 clients and produces over 500 different references. Each product is especially designed for the customer constituting a typical make to order setting [START_REF] Nahmias | Production and operation management[END_REF]. Currently the company uses a locally developed spreadsheet-based planning tool (called the Material Planning Module (MPM)) which checks the inventory for raw materials. If inventory is not enough to cover the order, the manager places an order to the carton supplier. Depending on the order size and the cardboard type, the supplier may or may not perform the first two operations (conversion and sizing) of the production process (see Figure 1) and deliver the cardboard cut in sheets. This decision is made by the manager during the material planning process. Further information about the aforementioned MPM can be found in [START_REF] Mendoza | Design of an integrated architecture for production planning in a printing company[END_REF].

The machine park is divided in 7 work centers, as seen on figure 1. Conversion and Sizing work centers are composed by a sheeter machine and an automatic guillotine stack cutter respectively. The function of these two centers is the conversion of cardboard rolls into cardboard sheets. As described earlier, for certain jobs the cardboard can be bought in sheets directly from the supplier, in that case the jobs do not go through the first to operations of the process. The following operations are printing, varnishing, diecutting, striping and gluing. These operations are executed in the flow direction shown in figure 1. Even though all jobs follow the same fabrication route, not all of them go through every work center. The route is given by the product design.

Figure 1: Workflow. Set up times are sequence dependent on the conversion, sizing, printing, varnishing and die-cutting workstations. In the case of the printing work center set up times vary from 32 to 70 minutes depending on the chosen sequence of operations; the case of the die-cutting center is even more critical, set up times can be zero or 75 minutes depending on the resulting production schedule. Set up times are measured continuously by the personnel and registered. Set up times are also assumed to be deterministic due the small variance observed in the data set. As presented on figure 1, printing and die-cutting centers have three printing presses and three die cutter machines each with different specifications. The printing quality levels, the maximum and minimum size of the sheet and the maximum caliber of the cardboard that can be cut, arise as constraints for the machines of these two centers. Because of its design, not all printable products can be processed on every press and not all the products that require cutting can be assigned to every die cutter machine. More than 85% of the products registered on the data base include a printing operation, between those; more than 70% required printing of at least two different colors. The three printing presses installed at the shop floor of the company are single color presses. The setup of these presses is one of the most time consuming activities and considerable savings can be achieved if jobs requiring the same color are processed consecutively. Summarizing, the scheduling problem to be solved can be characterized as a "flexible job shop framework" (See definition below).The main constraints are: sequence dependent set up times, machine eligibility constraints and recirculation. Due to managerial decisions preemptions are not allowed. From the optimization point of view this is a very hard problem to solve [START_REF] Rinooy | Machine scheduling problems: classification, complexity and computations[END_REF].

Problem description

From the scheduling theory point of view, the problem of sequencing operations in this production system can be framed as a Flexible Job Shop Scheduling Problem (FJSSP). Formally the FJSSP consists of a set J of n jobs with known operation times that are processed on a finite set I of m workstations; all operations for each job must be processed on a predefined order (routing). There may be one or more non-identical parallel machines at each work center. The sequence dependent setup time, skj is defined as the time needed to prepare a machine to execute job j when it is set to process job k. Finally, the set Mij is defined as the set of machines at workcenter i that can process job j (Machine eligibility).

Current scheduling practices

Information about processing and set up times was not taken into account in the scheduling process before the implementation of this production planning system. The production manager based on his experience constructs a schedule using a combined Fist in First out (FIFO) -Earliest Due Date (EDD) dispatching rule [START_REF] Panwalkar | A survey of scheduling rules[END_REF]. This process is done at the beginning of every week and takes between one and two hours depending on the number of orders to be scheduled. The main objective of the current scheduling practice is to meet the due dates for the most important customers. This objective is not measured in terms of a mathematical expression as the total weighted tardiness, or the total weighted number of tardy jobs or any due-date related objective describe on the literature, but rather with common service level indicators. Usually a high percentage of jobs are delivered on time (above 90% for 2006), but a large amount of overtime is usually needed to complete the production schedule. This occurs even though resource utilization rates are not as high as the manager may wish (around 70%). Literature FJSSP has addressed makespan as the classical objective function of this category of problems. Makespan can be defined as the completion time of the last job to leave the system and its minimization is commonly associated with high resource utilization [START_REF] Pinedo | Scheduling[END_REF] and maximization of throughput [START_REF] Damodaran | Mixed integer formulation to minimize makespan in a flow shop with batch processing machines[END_REF]. Currently due dates are being met at an acceptable rate, but some personnel believes that this is because the loose due dates quoted to the customers; it is coherent to think that this objective would still be accomplished at least at acceptable levels even if the objective function is not due date related. On other hand, maximizing utilization of resources by minimizing the makespan might reduce the cost of overtime. In fact, after brainstorming with the staff of the company, makespan was decided to be the objective function for the scheduling system.

2 DC-PRODUCTION PLANNING SYSTEM DC-Production planning system (DC-PPS) is a modular decision support system based on MS-Excel spreadsheets developed for the company. The core of the system consists of four databases (DB), two decision support (DS) modules and an ABC cost application as shown in figure 2.

Product Specification Database

The PSDB contains the design specifications of each product. Information includes data such as type and caliber of the cardboard, sheet dimensions, number of colors to print, glue type to be used and other design specifications. Each product record on the PSDB also contains the reference of the printing plates and dies and the machines where the product can be processed. This information permits the scheduling system to build the operation route and the machine eligibility restrictions for each job. The view of the product registration from is shown on figure 3.

Operation Time Database

The OPDB contains the information of the processing and setup times for each operation to be executed on the shop floor. Using a computer terminal installed on the shop area, a worker executing an operation registers through bar code tags the time actually spent on an operation. A record is automatically inserted on the Operation Time table (Figure 4). A materialized view of the table containing all the average process and set up times in each machine is updated every month. This view is the source of information used by the scheduling system. Orders are introduced on the system using the graphical user interface (GUI) shown on figure 5. To schedule an order, its status must have been set on "schedulable" on the MPM; the "schedulable" status is reached only when raw materials for an order are delivered by the supplier or confirmation of internal inventory availability is given by the MPM, this guarantees that all jobs have a release day of zero. The list of jobs to be schedule is built by selecting all jobs from the schedulable job pool in the MPM.

When the scheduling process begins, the system identifies the product code of each order and searches the corresponding database for the information of operations and machine eligibility to build the data structures to be used by the scheduling algorithm. Set up times are calculated in real time by the scheduling algorithm depending on the solution being evaluated.

It is also important to note that through the GUI on figure 5 the user may indicate to the scheduling algorithm which of the machines will be available for processing by checking the corresponding boxes. Jobs that can only be processed on not available machines are either dropped or considered for the next planning week.

Figure 5: DC-PPS Scheduler GUI

Scheduling Algorithm

The implemented scheduling method is based on the Simulated Annealing algorithm. Simulated Annealing (SA) is a local search meta-heuristic for combinatorial optimization problems [START_REF] Henderson | The theory and practice of simulated annealing. Handbook of meta-heuristics[END_REF] presented by Kirkpatrick in 1983 [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. The name is derived from its analogy with the annealing process in metallurgic. The annealing process consists of heating up a solid and then cooling it down slowly [START_REF] Pham | D Intelligent Optimization Techniques[END_REF]. As the solid cools down it goes through stages of quasi-equilibrium in which the temperature remains approximately constant. As the temperature decreases, the solid reaches states with lower energy levels. However there is a small probability of reaching states of higher energy. In terms of optimization a "state" corresponds to a solution. The energy level is analog to the value of the objective function. The algorithm proceeds by moving from higher energy states to states with lower energy levels. In order to avoid local optima the algorithm may choose (according to a probability) to move to states with higher energy levels. Such a probability increases with the temperature (or control factor) and decreases with the energy difference of any two states. The probability of moving to a higher energy level follows the Boltzmann and it is given by equation (1).

cT

E e E P ∆ - = ) ( (1)
Where E is the energy of the system, T is the current temperature and c the Boltzmann constant. As iterations of the simulated annealing algorithm are completed, the temperature decreases following a cooling schedule. When the temperature is "high" the search is diversified as more "bad" (solutions with higher energy levels) moves are allowed. On the other hand, when the temperature is low, fewer "bad" moves occur and the search is intensified. When designing a simulated annealing algorithm, four important factors must be taken into account [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]: (i) The objective function, (ii) the solution representation, (iii) the neighborhood design and (iv) the cooling schedule. Several schemes using different combinations of the above factors were tested; the ones selected and implemented on the SA on DC-PPS scheduler are presented next.

Objective function

As proposed in section 1.2 the objective function evaluated by the scheduler is makespan. Let J be the set of jobs, I the set of machines, N the set of all (i,j) operations, pi,j the processing time of job j on machine I and yi,j the starting time of job j on machine i. Makespan (denoted by Cmax) can be calculated as follows [START_REF] Pinedo | Scheduling[END_REF].

N j i p y C j i j i Max ∈ ∀ + ≥ ) , ( , , (2)
Every time a new solution is generated, the scheduler evaluates the objective function by calculating the completion time of each operation of all jobs in set J and storing the maximum value found.

Schedule representation

A Multi Permutation Representation (MPR) based on Genetic Vehicle Representation (GVR) [START_REF] Pereira | [END_REF] was selected. In the implemented MPR, c dynamic arrays contain the sequence in which jobs are to be processed on each of the c work centers of the shop. To evaluate the objective function, the MPR must be parsed into a schedule; this parsing is done by a special procedure named "Schedule Builder". The Schedule Builder checks each position (from first to last) of a permutation, sequencing the jobs on the corresponding work center on the same order. As explained on section 1.1, four out of seven work centers on the shop have more than one machine. In this case, the job that is being scheduled is assigned to the first available machine or worker (if the machine eligibility constraint is met). In the printing and Die-Cutting work centers when more than one machine is available, the job is assigned to the one with lowest machine load [START_REF] Koonce | Using data mining to find patterns in genetic algorithm solutions to a job shop schedule[END_REF]. If ties persist the job is assigned by lexicography. Table 1 shows the route of four actual products with modified processing times. Table 2 shows the machine eligibility constraint for the four products in Printing and Die-Cutting work centers. Figure 6 presents the MPR of a feasible solution for example 1. Figure 7 presents the solution after been parsed by the schedule builder. For simplicity all set up times in this example are assumed as zero.

Neighborhood design

Three different neighborhood designs based on two different types of moves [START_REF] Bozejko | Block approach tabu search algorithm for single machine total weighted tardiness problem[END_REF] (Insert and swap) were implemented and tested. Insert exchanges consist in randomly selecting two jobs j and k on a permutation, job k is then inserted on the position of job j. When k > j jobs from j to k-1 are moved one position forward on the permutation, otherwise jobs from j to k+1 are moved one position backwards. Swap exchanges require a pair of jobs j and k to be selected in a random fashion; In the exchange, job j takes the position occupied by job k on the permutation and job k is then sequenced on j position. Figure 7 shows both schemes applied to a single permutation selected also randomly.

A third neighborhood design consists on making swap exchanges on all the permutation of a solution simultaneously.

Initial solution

Three different generation schemes for the initial solution were tested, random generation and the well known Giffler and Thompson (G&T) enumerative algorithms for active and non-delay schedules [START_REF] Giffler | Algorithms for solving production scheduling problems[END_REF]. To break ties on the G&T, two suggested [START_REF] Chang | Ranking dispatching by data envelopment analysis on job shop environment[END_REF] priority dispatching rules are used. In this system Shortest Processing Time (SPT) and Most Work Remaining (MWR) were used.

Cooling schedule

The cooling schedule includes the initial temperature, a formula for changing the temperature and the stopping criterion. To set initial temperature, the scheduler uses the value of the objective function obtained of the initial solution and the value of the objective function of a randomly generated solution. The difference between these two values is taken as ∆E in (1), from where the value of T can be obtained by given P(E) a desired value.

As the intention of SA is to perform a diversified search on the first iterations, the given value of P(E) for the initial temperature calculations should be high [START_REF] Henderson | The theory and practice of simulated annealing. Handbook of meta-heuristics[END_REF]. For the DC-PPS scheduler this parameter was fixed on 95. The chosen formula to reduce the temperature is a stepwise reduction scheme known as the geometric cooling rule [START_REF] Pham | D Intelligent Optimization Techniques[END_REF]. Under this rule, K iterations are made at each temperature level, when such iterations are completed the temperature is reduced by a factor α (0 < α < 1). Let Ti be the current temperature, Ti+1 the updated value of temperature and α the cooling factor: The new temperature level is given by [START_REF] Nahmias | Production and operation management[END_REF].

i i T T α = +1 (3)
The stopping criterion is a predefined number of changes nt on the temperature level without improving the best solution found. Values for α, K, and nt have been fixed on 0.95, 10 and 1000 respectively. These values were set after a number of trial tests.

Output Data

The output data can be presented in two different modalities, the user can chose between a production program for each machine or a Gantt chart with the complete schedule of the plant (figure 8). To control production process the scheduling module includes a tool that allows the company to know the exact status of an order. A query to the Operation Time table of the OTDB, returns a data set that allows the scheduling system to present to the user the Gantt chart of the completed operations for an order; this is feature that allows to forecast the total the completion time of a job in case a customer wants information about his/her order.

Results

Implementation of the scheduling system has just been finished; databases are still being populated with information of all products and operations and the system has not entered operational mode yet. Experimentation with real instances shows promising results. An instance is defined as the pool of orders that must be process in a week; to test de system, the orders for the fifty weeks of the last year were considered, among those, ten weeks were randomly selected as benchmark instances. The best results in terms of the objective function were achieved using the non-delay schedule algorithm in combination with the MWR dispatching rule as the initial solution generation mechanism, and insert exchanges on a single machine as the neighbor design. This combination not only offers the best values for the objective function but also the best computational times. For each instance 10 were run on a Pentium M 1,67GH, 512Mb RAM computer with windows XP operative system. Table 4 summarizes the experiments on instance 1. Experimentation shows that the system outperforms the current scheduling method by 40% in terms of makespan as the due dates are still met at the current rates. Table 5 presents the results. ∑ j U is the number of tardy jobs [7].

CONCLUSIONS AND FUTURE RESEARCH

A low cost scheduling system for a small printing company was designed and implemented based on spreadsheet databases and VBA macros in MS Excel, to solve a flexible job shop problem with machine eligibility constraints, sequence dependent set up times and recirculation having the minimization of makespan as the objective function. Results are encouraging as the system outperforms the current scheduling method in use by over 40% in very reasonable computational times. This improvement in the utilization of the work centers is expected to reduce the amount of overtime currently hired by the company in order to meet the production program. The system also helps the company to control the execution of the production plan by implementing a computer tool to register the status of an order every time a production operation is complete on the shop floor. Reports on machine utilization and workers productivity can also be generated using this tool.

Database systems based on spread sheets like the one used on this system, can be a solution to small companies where there is a few data to be stored and there is not need to handle concurrency or transactions; If a system alike this is being consider to solve scheduling problems of a higher scope, it is strongly recommendable to support the databases on the appropriated database technology. On future research, it is the interest of the authors to use this experience as a start point to design a more general purpose spread sheet based system that can be used by other sector small companies. Also to implement more sophisticated scheduling algorithms that support multiple objective functions.

Figure 2 :

 2 Figure 2: DC-PPS Core 2.1 Relevant system components Both databases and DS modules are independent Excel workbooks linked by a main manager application. Two components are relevant for the proposed scheduling system, the Product Specification Database (PSDB) and the Operation Time Database (OPDB).

Figure 3 :

 3 Figure 3: DC-PPS Product specification input GUI

Figure 4 :

 4 Figure 4: DC-PPS Operation Time Database structure

Figure 6 :Figure 7 :

 67 Figure 6: MPR of a feasible solution for example 1

Figure 7 :

 7 Figure 7: Neighborhood design

Figure 8 :

 8 Figure 8: DC-PPS Scheduler output, Gantt chart

Table 1 :

 1 Example 1, Processing Times

	Job	C1 C2	C3	C4 C5 C6 C7
	1	5	5		10 10	5
	2			10/10	10	5	15
	3			10
	4	10 10	15	15 10

Where C1: Conversion, C2: Sizing, C3: Printing, C4: Varnishing, C5: Die-Cutting, C6: Stripping and C7: Gluing work centers respectively.

Table 2 :

 2 Example

		1, Machine Constraint
	Job	C3: Printing	C5: Die-Cutting
		PP1 PP2 PP3 DC1 DC2 DC3
	1		x	x	x
	2	x	x
	3	x
	4	x		x	x

Table 3 :

 3 Benchmark on test instances

			Current	Proposed
			Scheculing	Scheduling
	W Jobs	Method	System	Impvnt
			max C (h) ∑ j U	max C (h)	∑ j U
	1	8 53,294	0	37,009	0	44,00%
	2	8 58,192	0	43,105	0	35,00%
	3	7 51,936	0	34,856	0	49,00%
	4	5 70,247	1	52,423	1	34,00%
	5	8 48,104	0	36,721	0	31,00%
	6	13 54,403	2	38,044	1	43,00%
	7	5 59,013	0	40,145	0	47,00%
	8	10 64,391	1	48,053	0	34,00%
	9	11 60,47	0	42,287	0	43,00%
	10	11 60,55	1	42,049	0	44,00%
			Mean	0,054	-	0,028	40,40%

Table 4 :

 4 Computational experiments on test instance 1

ACKNOWLEDGMENTS

The authors would like to express their thankfulness to the staff of Impresos y Empaques D-Cartón Ltda. in Bucaramanga, Colombia.


Jorge E Mendoza
email: jorge.mendoza@uco.fr

Juan G Villegas
email: jvillega@udea.edu.co

A space biased-sampling approach for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists of designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distribution. We propose a metaheuristic that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set-partitioning formulation to sample the solution space and find solutions for the problem. Computational experiments show that our approach is competitive with state-of-the-art algorithms for the problem in terms of both accuracy and efficiency.

Introduction

In the vehicle routing problem with stochastic demands (VRPSD) a set of geographically-spread customers demand (or supply) a product that must be delivered (or picked-up) using a fleet of homogeneous vehicles located at a central depot. Each vehicle has a fixed and limited capacity, but the number of vehicles that can be used to service the demands is unlimited. The particular characteristic of the problem is that the exact quantities demanded (supplied) by each customer are only known upon the vehicle's arrival to the customer location (i.e., are stochastic). It is assumed, however, that each customer's demand follows an independent and known probability distribution. It is also assumed that the demand realizations (actual quantities) are nonnegative and less than the capacity of the vehicle.

The main effect of the stochastic demands is that if their realizations turn out to be larger than expected, the vehicle capacity may be exceeded leading to what is commonly known as a route failure. Different solution frameworks can be applied to deal with the uncertain demands in the VRPSD [START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF]. Among these frameworks, the most widely used in the literature, and the one we selected for this research, is two-stage stochastic programming. As it name suggests, this framework solves the VRPSD in two stages. In the first stage, a set of planned routes is designed. Each route is a tour starting and ending at the depot after visiting a set of customers. In the first-stage solution, each customer must be visited by exactly one vehicle (route) and the total expected demand serviced by each vehicle cannot exceed its capacity. In the second stage, each planned route is executed until a route failure occurs. Upon failure, a recourse action is applied to recover the feasibility of the failing route. The recourse action is classically defined as a return trip to the depot to restore the capacity of the vehicle, followed by a trip back to the customer location to complete the service. After service completion, the route is resumed from that point on as originally planned. The second stage solution is then the actual set of routes traveled by the vehicles. It is worth noting that the literature accounts for more sophisticated recourse actions; nonetheless, we decided to keep the classical policy because: it is simple, suitable to many practical applications, and it allows a more direct comparison with previously published results. Solving the two-stage stochastic program for the VRPSD consists in selecting in the first stage the set of planned routes that minimizes the expected cost of the second stage solution. For details on the computation of the expected cost of the second stage solution the reader is referred to [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Laporte | An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF].

Solution approaches for the VRPSD based on the two-stage stochastic programming formulation described above include both exact [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF][START_REF] Laporte | An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF] and heuristic [START_REF] Goodson | Solution methodologies for vehicle routing problems with stochastic demand[END_REF][START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF] methods. As it is often the case in combinatorial optimization problems, exact methods for the VRPSD are limited to solve small-size instances, thus industrial-scale problems should be tackled using heuristic approaches. To the best of our knowledge, the two most recently-published heuristic approaches for the VRPSD are the look-ahead heuristics by Mendoza et al. [START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF] and the simulated annealing by Goodson [START_REF] Goodson | Solution methodologies for vehicle routing problems with stochastic demand[END_REF]. The former, are a set of fast, simple, and effective constructive procedures; while the latter is a performing metaheuristic that embeds sophisticated neighborhood schemes. This paper proposes a new heuristic approach that uses randomized heuristics for the traveling salesman problem (TSP), a route partitioning procedure, and a set-partitioning model, to sample the solution space and find high-quality solutions for the problem.

Space biased-sampling

When solving the VRPSD (and VRPs in general) one often works with elements that belong to four sets: i) the set of solutions, S; ii) the set of feasible routes, R; iii) the set of feasible clusters of customers, C; and iv) the set of TSP-like tours (i.e., giant tours visiting all customers), P. Heuristic approaches generally rely on searching elements in one set and then mapping them to an element in the set of solutions. For instance, cluster-first, route-second approaches consist in using some procedure to select a sub-set of elements from C and then apply another procedure to map the selected elements to a single element in set S. More elaborate approaches map elements from different sets iteratively. One good example is Prins' well-known evolutionary algorithm for the capacitated VRP [START_REF] Prins | A simple and effective evolutionary algorithm for the vehicle routing problem[END_REF]. At each iteration, the algorithm selects two elements from P and applies to them a crossover operator to obtain a new element. The new element is mapped to an element in S using the split procedure. Then, local search is applied to the mapped element trying to identify a new (better) element. When local search is completed, the new element is mapped back to P using a concatenation procedure and the whole routine starts over. In both cases, one-time or iteratively mapping, the effectiveness of the methods is highly dependent on the procedures used to select elements from the sets and the procedures used to map elements between sets.

The metaheuristic proposed in this paper works in two phases. In the first phase, it samples T elements from the set of TSP-like tours (i.e., P) and maps each sampled element p to a sub-set W p in the set of feasible routes (i.e., R). In the second phase, the approach maps a set W ⊂ R, where W = W 1 ∪ . . . ∪ W T , to one element s ∈ S by solving a set-partitioning formulation of the problem.

To sample elements from P, our approach uses a set of 4 randomized TSP heuristics, namely, nearest neighbor (NN), nearest insertion (NI), best insertion (BI), and farthest insertion (FI). The four heuristics follow the same principle: at each iteration they grow a tour by selecting a non-visited customer and connecting it to the circuit. Each heuristic, however, uses a different decision rule to select and connect customers. To produce randomized versions of the four heuristics we simply allow each procedure to randomly select the connecting customer between the K top-ranked customers according to its original decision rule. Since there exist TSP-like tours that our randomized heuristics cannot build, we say that our metaheuristic does a biased sampling of set P.

To map each sampled element p to its corresponding W p ⊂ R our approach uses the s-split procedure for the VRPSD [START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF]. S-split was originally proposed to map an element in P to an element in S by optimally partitioning the giant tour into a set of feasible routes that form a VRPSD solution. Nonetheless, s-split accomplishes its mission by running a dynamic programming algorithm that evaluates every single feasible route that can be obtained from the giant tour without altering the order of the customers. In other words, by saving a reference to the set of routes evaluated by s-split while partitioning p, we obtain a mapping of p to a sub-set W p ⊂ R. Since we also obtain a mapping of p to a solution s ∈ S, we keep a reference to the best solution observed during the sampling phase to have a good upper bound in the second phase of our metaheuristic.

In the second phase, our approach maps the set W = W 1 ∪ . . . ∪ W T to a solution s ∈ S by solving a set-partitioning formulation (model) of the VRPSD. In the model we: define one binary decision variable for each feasible route in W; set the coefficient of each variable in the objective function as the expected cost of the associated route; and set constraints guaranteeing that each customer will be visited by exactly one route. The objective is then to select the best sub-set of routes from W to build the solution reported by our approach. It is well known that VRPs can be modeled as set-covering/set-partition problems, but researchers often underestimate the benefits of embedding this approach within metaheuristics. Recently, authors like Villegas [START_REF] Villegas | Vehicle routing problems with trailers[END_REF] have shown that applied as a post-optimization procedure, a set-partitioning model may lead to significant improvements in the quality of final solutions. In the proposed approach, the set-partitioning model is an integral part of the method rather than only a post-optimization strategy.

Computational experiments

We implemented our approach in Java (jre V.1.6.0 22-b04) and used the Gurobi Optimizer (version 4.0.1) for solving the set-partitioning model. To test the effectiveness of our approach, we ran it on the 40-instance testbed proposed by Christiansen and Lysgaard [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF]. The instances range from 16 to 60 customers and assume Poisson distributed customer demands. For each instance we compared our solution with the best known solution (BKS) which is due to either [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF], [START_REF] Goodson | Solution methodologies for vehicle routing problems with stochastic demand[END_REF], [START_REF] Mendoza | Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands[END_REF], or to the three of them. It is worth mentioning that [START_REF] Christiansen | A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands[END_REF] provided optimality certificates for 19 out of the 40 instances. For the experiment, we set parameter T to 6, 000 and draw T 4 samples using each randomized heuristic. The parameter K of the heuristics was set to 6 for NI, BI, FI, and to 3 for NN.

The results of our experiment show that the proposed approach is effective to solve the VRPSD. On the instances with proven optimum, our method matched the optimal solution on 10 out of 19 instances and delivered solutions with optimality gaps ranging from 0.02% to 0.92% (with an average of 0.50%) on the remaining 9. On the 21 instances without provably optimal solution, our method unveiled 2 new best known solutions and matched another 4. On the remaining 15 instances, our approach provided solutions with gaps (with respect to BKSs) ranging from 0.01% to 1.88% (with an average of 0.56%). These are remarkable results taking into account the absence of a local search procedure, a component that is often essential to build competitive VRP metaheuristics. The experiment also shows that our approach is competitive in terms of computational efficiency. Our method reported execution times ranging from 4 seconds to 161 seconds1 , with an average running time of 47.37 seconds. To illustrate, on the same testbed Goodson reported for his simulated annealing [START_REF] Goodson | Solution methodologies for vehicle routing problems with stochastic demand[END_REF], implemented in C++, minimum and maximum execution times of 9s and 603s, respectively (average 268s) 2 . In conclusion the proposed approach is competitive with state-of-the-art algorithms for the VRPSD in terms of both quality and efficiency.

Research currently underway includes the implementation of new randomized heuristics to foster more diversification and local search procedures to add some intensification to the sampling phase.

Udine, Italy, July 25-28, 2011

On a 3.0GHz Intel Pentium Core Duo processor with 3GB of RAM, running Windows XP professional.

On a 2.8GHz Intel Xeon X5660 processor with 12GB of RAM, running the CentOS 5.3 operating system.


Jorge E Mendoza
email: jorge.mendoza@uco.fr

Louis-Martin Rousseau

Juan G Villegas
email: jvillega@udea.edu.co

On the vehicle routing problem with stochastic demands and duration constraints: formulations and a hybrid metaheuristic approach

The vehicle routing problem with stochastic demands (VRPSD) consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. In this research we present two strategies to deal with route duration constraints in the VRPSD. To solve the resulting problem, we proposed a greedy randomized adaptive search procedure (GRASP) with a post optimization procedure. The GRASP component uses a set of randomized route-first, cluster-second heuristics to generate starting solutions and a variable neighborhood descent (VND) procedure to carry on the local search phase. The post optimizer selects the best possible routes to assemble the final solution from the set of all routes found in the local optima reached by the GRASP. We discuss extensive computational experiments analysing the cost of considering route duration constraints on the VRPSD. In addition, we report state-of-the-art solutions for a established set of benchmarks for the classical VRPSD.

Introduction

The vehicle routing problem with stochastic demands (VRPSD) can be defined on a complete and undirected graph G = (V, E), where V = {0, . . . , n} is the vertex set and E = {(v, u) : v, u ∈ V, v ̸ = u} is the edge set. Vertices v = 1, . . . , n represent the customers and vertex v = 0 represents the depot. A weight t e is associated with edge e = (v, u) = (u, v) ∈ E, and it represents the travel time between vertices v and u. Each customer v has a random demand ξ v for a given product. Customer demands are met using an unlimited fleet of homogeneous vehicles with capacity Q located at the depot. The exact quantity demanded by each customer is not known until the vehicle arrives at the customer location. It is assumed, however, that each customer's demand follows an independent and known probability distribution and that all demand realizations (actual quantities) are nonnegative and less than the capacity of the vehicle.

The VRPSD is classically formulated as a two-stage stochastic program. In the first stage, a set R of planned routes is designed. Each route r ∈ R is a sequence of vertices r = (0, v 1 , . . . , v i , . . . , v nr , 0), where v i ∈ V \ {0} and n r is the number of customers serviced by the route. During the planning phase, each route is designed so that the total expected load does not exceed the capacity of the vehicle (i.e.,

∑ v∈r\0 E[ξ v ] ≤ Q ∀ r ∈ R
) and every customer is visited by exactly one route. In the second stage, each route is executed until a route failure occurs, that is, the capacity of the vehicle is exceeded. A recourse action is then applied to recover the feasibility of the failing route. The recourse action is defined as a return to the depot to reload the vehicle, followed by a trip back to the customer location to complete the service. The route is then resumed from that point as originally planned. The second-stage solution is then the actual set of routes traveled by the vehicles. The problem consists in determining during the first stage the set of planned routes R that minimizes the total expected travel time of the routes in the second-stage solution

E [ T (R) ] = ∑ r∈R E [ Tr ]
, were Tr is the (random) duration of route r, and E[•] denotes the expected value.

The VRPSD with duration constraints (VRPSDDC) extends the problem to include a maximum route duration T for each planned route r ∈ R. Different strategies can be applied to deal with duration constraints. For instance, [START_REF] Yang | Stochastic vehicle routing with restocking[END_REF] enforces the duration constraint on the expected duration of each planned route (i.e., E

≤ T ∀r ∈ R); [START_REF] Erera | The vehicle routing problem with stochastic demands and duration constraints[END_REF] imposes a hard constraint on the second-stage duration of the route, meaning that planned routes should verify the constraint for any possible vector of demand realizations; and [START_REF] Tan | Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation[END_REF] penalizes violations of the duration constraint in an additional objective function, driver remuneration, and solve the problem as a multiobjective optimization problem with posterior articulation of preferences. In this research we introduce two alternative strategies.

Note that since all demand realizations are less than the capacity of the vehicle, the maximum number of failures in a route is n r -1. Consequently, the total duration of a route Tr follows a discrete distribution with 2 nr-1 possible outcomes. Let us refer to each possible outcome for Tr as a duration profile. Let us also denote as P r the set of all duration profiles for route r and as T p r the total duration of the route if profile p ∈ P r is observed. Note also that if demands follow additive probability functions, as it is classically assumed in the VRPSD literature, the probability of having a route failure while visiting each customer of a given route can be analytically computed (see for instance [START_REF] Mendoza | A multi-space sampling heuristic for the vehicle routing problem with stochastic demands[END_REF] for details on how to calculate such probability). Knowing these failure probabilities, allows us to compute the probability P r(p) of observing each duration profile p ∈ P r . We propose a tractable algorithm to compute P r and P r(p) ∀p ∈ P r .

Our first strategy, hereafter referred to as CC, consists in enforcing the duration constraint as a chance constraint, meaning that P r( Tr ≤ T ) ≥ 1-β ∀r ∈ R, where β ∈ [0, 1] is a preset threshold. Our second strategy, henceforth DR, consists on implementing a recourse action to recover from violations of the duration constraint. The considered recourse action is simply to pay the drivers overtime. Therefore, during the first stage, we minimize

E [C] = ∑ r∈R [ E[ Tr ] + ∑ p∈Pr|T p r >T ϕ ((T p r -T ) × P r(p)) ]
, where ϕ(•) is a function to compute the cost of the expected overtime. Note that in our approaches β and ϕ(•) may be adapted to capture the decision maker's aversion towards violations of the duration constraint.

GRASP with heuristic concentration

Algorithm 1 GRASP+HC: General structure 1: function GRASPHC(G,H,K) 2:

Ω ← ∅, k ← 1 3: while k ≤ K do 4:
for h ∈ H do 5:

tps k ←startSolution(h, G) 6: s k ←split(G, tsp k ) 7: s k ←vnd(G, s k ) 8: s * ←update(s k , s * ) 9: for r ∈ s k do 10: Ω ← Ω ∪ r 11:

17: end function

To solve our two formulations for the VRPSDDC, namely CC and DR, we developed a greedy randomized adaptive search procedure (GRASP) enhanced with heuristic concentration. Algorithm 1 describes the proposed approach. At each GRASP iteration k (lines 3-14) the algorithm selects a randomized TSP heuristic h from a set H and uses it to build a giant TSP tour tsp k visiting all customers (line 5). Then, the algorithm uses an adaptation of the s-split procedure for the VRPSD [START_REF] Mendoza | A multi-space sampling heuristic for the vehicle routing problem with stochastic demands[END_REF] to optimally partition tsp k into a set of feasible routes that make up a starting solution s k (line 6). Next, the algorithm uses the Singapore, August 4-8, 2013 first-improvement versions of the re-locate and 2-opt neighborhoods to perform a variable neighborhood descent (VND) from the starting solution s k (line 7). At the end of iteration k, the algorithm updates the best solution s * (line 8) and adds the routes of the local optimum (i.e., s k ) to a set Ω (lines 9-11). After K iterations the GRASP stops and the heuristic concentration (HC) takes place. In this phase, our method uses a commercial optimizer to solve a set-partitioning formulation over the set of routes Ω (line 15). To speed up the HC phase, the algorithm uses the objective function of the best solution found by the GRASP as an initial upper bound for the set-partitioning problem. Note that the concrete implementations of split(•), vnd(•), and select(•) slightly vary depending on the formulation (i.e., CC or DR) being solved while the implementations of startSolution(•) and setPartitioning(•) remain unchanged.

Computational experiments

To the best of our knowledge, there are not publicly-available benchmarks for the VRPSDDC. To build a set of instances, we first ran 10 times our GRASP+HC on each of the 40 Christiansen-and-Lysgaard VRPSD benchmarks. We obtained solutions with a maximum gap of 0.03% with respect to the best known solutions (BKSs) which are 38 optimal solutions reported in [START_REF] Gauvin | Un algorithme de génération de colonnes pour le problème de tournées de véhicules avec demandes stochastiques[END_REF] and 2 heuristic solutions reported in [START_REF] Mendoza | A multi-space sampling heuristic for the vehicle routing problem with stochastic demands[END_REF]. From each of the 40 VRPSD instances we built a VRPSDDC instance by setting T = max{E [ Tr ]|r ∈ R}, where R is the best solution found for the original VRPSD instance. Note that the solutions we found for the original VRPSD instances are the same we would have found if we solve the new VRPSDDC instances dealing with duration constraints as proposed in [START_REF] Yang | Stochastic vehicle routing with restocking[END_REF], that is, enforcing E

[ T ]
≤ T ∀r ∈ R. For the sake of brevity we will henceforth refer to the latter formulation as ED. In our first experiment, we ran GRASP+HC on CC setting β = 0.05. The results show that, as expected, CC leads to solutions that are more robust to violation of the duration constraint than those obtained by ED. For instance, on CC solutions, the maximum probability of failing the duration constraint for a single route is 4.94% while the same figure is 44.63% on ED solutions. Our data also suggest that this improvement in the robustness is obtained with only small increments on the expected cost of the solutions (an average 3.6%). In our second experiment we analyse the behavior of ED solutions when there are costs associated to violations of the duration constraints. We evaluated a posteriori our ED solutions using objective function E[C] with three different ϕ(•) functions (linear, piece-wise linear, and quadratic) and compared the results with those delivered by GRASP+HC running on DR (with the same ϕ(•) functions). The results show that ED leads to solutions that not only have high probabilities of violating the duration constraints (as concluded in our first experiment) but that also become expensive when there are cost associated to the magnitude of those violations.


Marc Brunelle

James Kirby

Alexis Michaud

Justin Watkins

Prosodic systems: Mainland Southeast Asia

Mainland Southeast Asia is often viewed as a linguistic area where five different language phyla -Austroasiatic, Austronesian, Hmong-Mien, Sino-Tibetan and Kra-Daihave converged typologically. This chapter illustrates areal features found in their prosodic systems, but also emphasizes their oft-understated diversity.

The first part of the chapter describes word level prosodic properties. A typology of word shapes and stress is first established: we revisit the concept of monosyllabicity, go over the notion of sesquisyllabicity (as typified by languages like Mon or Burmese) and discuss the realization of alternating stress in languages with polysyllabic words (such as Thai and Khmer).

Special attention is then paid to tonation. Although many well-known languages of the area have sizeable inventories of complex tone contours, languages with few or no tones are common (20% being atonal). Importantly, the phonetic realization of tone frequently involves more than simply pitch: properties like phonation and duration often play a role in signaling tonal contrasts, along with less expected properties like onset voicing and vowel quality. We also show that complex tone alternations (spreading, neutralization and sandhi processes), although not typical, are wellattested.

The second part of the chapter addresses the less well-understood topic of phrasal prosody: prosodic phrasing and intonation. We reconsider the question of the amount of conventionalized intonation in languages with complex tone paradigms and pervasive final particles. We also show that information structure is often conveyed by means of overt markers and syntactic restructuring, but that it can also be marked by means of intonational strategies.

1.

Scope of the chapter Mainland Southeast Asia (MSEA) is often defined as a Sprachbund, a linguistic area where languages from five different phyla (Austroasiatic, Austronesian, Hmong-Mien, Kra-Dai and Sino-Tibetan) converge and develop similar structures [START_REF] Matisoff | Tonogenesis in Southeast Asia. Consonant Types and Tone[END_REF][START_REF] Alieva | A Language-Union in Indo-China[END_REF][START_REF] Enfield | Linguistic epidemiology : semantics and grammar of language contact in Mainland Southeast Asia London[END_REF][START_REF] Brunelle | Register in Eastern Cham: Phonological, Phonetic and Sociolinguistic approaches[END_REF] 1 . While convergence processes are easy to identify in the region, its geographical boundaries are ill-defined, and one should not understate its typological diversity [START_REF] Henderson | The Topography of Certain Phonetic and Morphological Features of Southeast Asian Languages[END_REF][START_REF] Brunelle | Register in Eastern Cham: Phonological, Phonetic and Sociolinguistic approaches[END_REF]Kirby 2016, Kirby and[START_REF] Kirby | Southeast Asian tone in areal perspective. The Cambridge handbook of areal linguistics[END_REF]. In this chapter, we cover the area encompassing the Indochinese Peninsula (Vietnam, Cambodia, Laos, Thailand, Myanmar and Malaysia), but also include Guangxi and Yunnan in Southern China (excluding Chinese varieties, covered in Chapter XXX) and Northeast India. As Austronesian languages are covered in a separate chapter, our discussion of this phylum is limited to Chamic languages spoken in Vietnam and Cambodia, and to Austronesian languages of the Malay peninsula.

Our main goal is to give an overview of representative types of word-level ( §2) and phrase-level prosody ( §3), highlighting areas of convergence between families, without understating their diversity.

Word-level prosody

In this section, we first discuss the most common word shapes and stress patterns found in MSEA ( §2.1). As these two properties are largely dependent, they are discussed together. We then give an overview of the diverse tonation systems of the region ( §2.2).

Word shapes and stress

The basic vocabulary of many MSEA languages is monosyllabic. This is the case in most Kra-Dai and Hmong-Mien languages, but also in Vietnamese, an Austroasiatic language. However, in most of these languages, a significant part of the lexicon is made up of compounds, and most languages also have some polysyllabic loanwords. This can be illustrated with Vietnamese. The Vietnamese basic lexicon is largely monosyllabic, as illustrated in (1). Our transcriptions follow the transcription conventions in [START_REF] Kirby | Vietnamese (Hanoi Vietnamese)[END_REF], except for the tone notation.

( By definition, monosyllabic words cannot bear paradigmatic or syntagmatic word stress.

However, even in languages whose core lexicon is monosyllabic, polysyllabic words can have fairly complicated stress patterns. While Vietnamese polysyllables do not seem to show any type of word-level prominence [START_REF] Kirby | Southeast Asian tone in areal perspective. The Cambridge handbook of areal linguistics[END_REF], the Indic loanwords of many Southeast Asian languages have alternating stress systems that are not necessarily attested in their native lexicon [START_REF] Luangthongkum | Rhythm in standard Thai: University of Edinburgh[END_REF][START_REF] Potisuk | F0 correlates of stress in Thai[END_REF][START_REF] Potisuk | Acoustic correlates of stress in Thai[END_REF][START_REF] Green | Word, foot, and syllable structure in Burmese[END_REF]. For instance, polysyllabic Thai words show a tendency to alternating iambic stress, stress clash avoidance and the application of the stress-to-weight principle, as illustrated in ( 6).

( In these Thai polysyllables, stress is realized primarily through longer duration. The tones of stressed syllables are also realized more fully, while those of unstressed syllables are raised and partially neutralized [START_REF] Potisuk | Acoustic correlates of stress in Thai[END_REF].

Many MSEA languages also have a canonical sesquisyllabic word shape, a structure typical of the region. The concept of sesquisyllable seems to be attributable to [START_REF] Henderson | The main features of Cambodian pronunciation[END_REF], but the te was oined b Ja es Matiso ( 973) to designate wo ds ontaining "one s llable and a hal " Gene all -speaking, a sesquisyllable is a disyllable with an iambic stress pattern. Its unstressed first syllable is called the minor syllable or the presyllable, and has a reduced phonological inventory and a limited array of possible syllable structures. Its stressed second syllable has the full array of possible contrasts of the language and can have a more complex syllable structure.

Sesquisyllables show variation across and sometimes even within languages. [START_REF] Thomas | On sesquisyllabic structure[END_REF] argues that there are four types of sesquisyllables. In the first type, a fully predictable schwa is inserted in some clusters, as in the Khmer word ក្បាល [kəɓaːl] 'head' whi h is unde l ingl /kɓaːl/ Most autho s onside su h ases as onos llables athe than sesquisyllables and treat their schwa as an excrescent vowel [START_REF] Thomas | On sesquisyllabic structure[END_REF][START_REF] Butler | Deconstructing the Southeast Asian sesquisyllable: A gestural account[END_REF] Interestingly, the trochaic mirror image of sesquisyllables, namely disyllables with an initially stressed syllable and a reduced second syllable, does not seem attested in MSEA.

Many languages of the area also have a non-sesquisyllabic polysyllabic structure as their canonical word shape. One example is Malay, a language that tends to have disyllabic roots, but can have much longer grammatical words because of affixation or loans from Indic or Western languages. Careful analysis strongly suggests that Peninsular Malay does not have word stress [START_REF] Don | How words can be misleading: a stud o s llable ti ing and "st ess[END_REF]. Many Sino-Tibetan languages can also be shown to be polysyllabic because segmental or tonal processes affect their prosodic words. In Qiang and Shixing, for instance, the lenition of word-medial consonants provides positive evidence for polysyllabic prosodic words [START_REF] Lapolla | A Grammar of Qiang with annotated texts and glossary[END_REF]Huang 2003: 31-32, Chirkova 2009: 12-13).

Tonation

Many Southeast Asian languages employ one or more contrastive laryngeal properties that we term tonation (following Bradley 1982). This includes not only the use of pitch but also properties such as vowel quality, voice quality, intensity, and/or duration. The extent to which it is useful to sub-typologize languages according to exactly which property or properties they (canonically) employ remains a matter of some debate (Abramson & Luangthongkum 2009;[START_REF] Dicanio | The Phonetics of Register in Takhian Thong Chong[END_REF][START_REF] Enfield | Linguistic diversity in mainland Southeast Asia. Dynamics of human diversity: The case of mainland Southeast Asia[END_REF][START_REF] Gruber | An Acoustic, Articulatory, and Auditory Study of Burmese Tone: Georgetown PhD dissertation[END_REF]Brunelle & Kirby 2016); despite this, we have broadly organized the following sections by phonetic property in order to emphasize the diversity and phonetic variability of the region's wo d-level prosodic systems.

Inventories

Around 20% of the languages spoken in MSEA are completely atonal [START_REF] Brunelle | Re-assessing tonal diversity and geographical convergence in Mainland Southeast Asia[END_REF]. These languages are virtually all either of Austronesian or Austroasiatic stock. Diversity is greater in Austroasiatic, while Austronesian languages of MSEA are either atonal or have simple tonation-type properties2 .

Many languages of the area, especially in the Austroasiatic and Austronesian phyla, have been des ibed as having ' egiste s' ende son ( 95 ) was the first author to employ the term register to e e to a 'bundle' o (b oadl su aseg ental) eatu es su h as honation t e it h vowel quality, intensity, and vowel duration, leading to the designation of (voice-)register languages in the Southeast Asian linguistic literature [START_REF] Henderson | The main features of Cambodian pronunciation[END_REF][START_REF] Gregerson | Tongue-root and Register in Mon-Khmer[END_REF][START_REF] Ferlus | Formation des Registres et Mutations Consonantiques dans les Langues Mon-Khmer[END_REF][START_REF] Diffloth | Registres, Dévoisement, Timbres Vocaliques: leur Histoire en Katouique[END_REF]. Register is normally understood to arise from the neutralization of voicing in onsets and subsequent phonologization of phonetic properties originally associated with voicing.

A hallmark of register systems is redundancy, in the sense that one can identify multiple co-occurring properties. The Austroasiatic language Mon is an example of a canonical register system relying on pitch and phonation, but also on vowel quality and duration [START_REF] Lee | An acoustical study of the register distinction in Mon[END_REF]Diffloth 1985;[START_REF]Another Look at the Register Distinction in Mon[END_REF]Abramson et al. 2015). Another example is Wa, a Mon-Khmer language spoken in north-eastern Myanmar and in the south-west of Yunnan province in China, that distinguishes two lexical registe s te ed ' lea ' and 'b eath ' (Watkins 00 )

In Wa, vowels in breathy register are characterised principally by their relatively breathier phonation type than the modal phonation of clear register vowels, illustrated in (9). In addition, there are typically differences such that clear register vowels have slightly higher pitch than breathy register vowels. Vowel duration and vowel quality are mostly insignificant with respect to Wa register, though for some speakers there may be contrasts in these quality differences. been documented for several dialects of Khmu [START_REF] Suwilai | Register complex and tonogenesis in Khmu dialects[END_REF][START_REF] Svantesson | Tone production, tone perception and Kammu tonogenesis[END_REF][START_REF] Abramson | Voice register in Kh u': Ex e i ents in odu tion and e e tion Phoneti a[END_REF]. Restructuring can also lead to the development of a large vowel inventory, as apparently occurred in the history of Khmer [START_REF] Huffman | The register problem in fifteen Mon-Khmer languages[END_REF] or Haroi [START_REF] Lee | Devoicing, Aspiration, and Vowel Split in Haroi: Evidence for Register (Contrastive Tongue-Root Position)[END_REF][START_REF] Mundhenk | Haroi Phonemes[END_REF].

We an ont ast egiste s with tone invento ies based on u e it h B ' u e' it h we mean to refer to a system in which pitch is the only phonetic exponent of a suprasegmental tonation contrast. A good example of such a language in MSEA might be Southern Vietnamese (B unelle 009b Gsell 9 0 ũ 1982). However, setting aside restructured register languages such as Khmu, it is not clear if such systems actually exist, and if they do, they may in fact be rather rare: it seems reasonable to assume that there are always at least low level spectral effects esent in ' u e' it h s ste s. In any case, it is probably still possible to differentiate between tone systems where these spectral effects are redundant, and those systems where they are a necessary element of patterns of tone contrasts, as detailed in the following section.

A related issue here concerns the phonological analysis of primarily pitch-based tone systems. The languages of sub-Saharan Africa provide compelling evidence for an analysis based on sequences of level tones (from two, High and Low, to as many as five levels; see Chapter XXX). In Asia, such systems appear to be significantly less common (see [START_REF] Evans | African tone in the Sinosphere[END_REF] for an overview), though cases do exist such as Pumi [START_REF] Jacques | Tonal alternations in the Pumi verbal system[END_REF][START_REF] Daudey | A grammar of Wadu Pumi[END_REF][START_REF] Ding | A Grammar of Prinmi: Based on the central dialect of Northwest Yunnan, China: Brill. Đỗ hế Dũng hiên ương n & Geo ges Boulakia 99 Intonation in ietna ese Intonation systems: A Survey of Twenty Languages[END_REF] and Yongning Na (Michaud 2017: 87-101). Evidence for this type of decompositional analysis comes primarily from morphotonological alternations (see §2. 2009b). Hmong-Mien languages also tend to exhibit systems of this type [START_REF] Huffman | Measures of phonation type in Hmong[END_REF][START_REF] Andruski | Phonation types in production of phonological tone: the case of Green Mong[END_REF][START_REF] Esposito | An acoustic and electroglottographic study of White Hmong tone and phonation[END_REF][START_REF] Garellek | Voice quality and tone identification in White Hmong[END_REF][START_REF] Garellek | Relative importance of phonation cues in White Hmong tone perception[END_REF]. For example, Black Miao, a Hmong-Mien language spoken in Guizhou province, China, contrasts five level tones, but three of these tones are also respectively characterized by laryngealized, tense, or breathy phonation, all of which are important cues for accurate native-speaker discrimination [START_REF] Kuang | The tonal space of contrastive five level tones[END_REF]. Although strictly speaking outside of MSEA proper, a number of Wu languages spoken in China also have mixed phonation/pitch tonation systems [START_REF] Rose | On the non-equivalence of fundamental frequency and linguistic tone[END_REF]).

These languages are perhaps especially notable o e lo ing 'whis e ' and/o 'g owl' phonation types, probably involving oscillation of epilaryngeal structures [START_REF] Edmondson | The aryepiglottic folds and voice quality in the Yi and Bai languages: laryngoscopic case studies[END_REF]).

2.2.2

Tonal phonology, tone sandhi and morphotonology one se ves a wide ange o un tions in the wo ld's languages: in addition to its phonemic function, it can mark grammatical categories; it can be assigned according to paradigm-specific rules; and it can even constitute the sole phonological form of a morpheme (see Chapter XXX Word Prosody II: Tone systems). In MSEA, the vast majority of Austroasiatic, Austronesian and Tai-Kadai tone languages have "ine t" tones (tones that a e not a tive in honolog o morphology), whereas productive tonal processes are more commonly found in some Hmong-Mien and Sino-Tibetan languages.

The first type of tone process found in the area is tone sandhi in its narrow sense: a tone turns into another contrastive tone in a specific tonal environment. For instance, White Hmong has seven tones, out of which five undergo the permutations in (11) in most compounds and some phrases. This tone sandhi seems partly fossilized in contemporary White Hmong, but there is little doubt that it was productive at an earlier stage of the language [START_REF] Ratliff | Tone sandhi compounding in White Hmong[END_REF][START_REF] Mortensen | The Development of Tone Sandhi in Western Hmongic: A New Hypothesis[END_REF]).

(11) White Hmong tone sandhi [START_REF] Ratliff | Tone sandhi compounding in White Hmong[END_REF] 52, 22, 31ʔ → 24 → 33 / 55, 53 _____

→ 22

Tone sandhi must be distinguished from tonal coarticulation, which could be characterized as phonetic accommodation between adjacent tones. Studies of tonal coarticulation in Central

Thai and Vietnamese suggest that progressive coarticulation is much stronger than regressive, and that assimilatory effect are more common than dissimilatory ones in these languages [START_REF] Han | Phonetic variation of Vietnamese tones in disyllabic utterances[END_REF]Gandour et al. 1992b;1992a;1994;Brunelle 2009a). Tone sandhi could develop from the misinterpretation of some forms of tone coarticulation, but this seems to require more than simple phonologization [START_REF] Michaud | Information Structure in Asia: Yongning Na (Sino-Tibetan) and Vietnamese (Austroasiatic). The Oxford Handbook of Information Structure[END_REF].

The most complex sandhi-like processes in the region are doubtless found in the Kuki-Chin languages of Burma, Mizoram and Nagaland. In these languages, combinations of tone spreading and positional tone sandhis sensitive to the boundaries of prosodic domains are commonplace [START_REF] Hyman | Tone and syllable structure in Hakha-Lai[END_REF]2004;[START_REF] Watkins | A first account of tone in Myebon Sumtu Chin[END_REF]). In the Tibeto-Burman southern Chin language Sumtu, of which the Myebon dialect is described by Watkins ( 2013 A second type of tone alternation is tone spreading, a process observed in some level-tone systems: for instance, in Yongning Na (Sino-ibetan) L tone s eads og essivel ("le t-toight") onto s llables that a e uns e i ied o tone (Mi haud 0 7: 3 ) Spreading of level tones is a process of phonological copying; this needs to be distinguished from cases where the domain of phonetic realization of a lexical tone category is the entire phonological word, as in Tamang (Sino-Tibetan). The four tones of Tamang unfold over an entire phonological word: non-initial syllables of words, whether they be a suffix or part of a single morpheme, never carry their own tone, so that their f 0 curve can be considered an expression of the tone lexically carried by the initial lexeme, which is allowed to unfold over the available space --the entire phonological word [START_REF] Mazaudon | Tonal Contrasts and Initial Consonants: A Case Study of Tamang, a 'Missing Link' in Tonogenesis[END_REF]. This can usefully be distinguished from tonal coarticulation on toneless syllables, as illustrated by Northern Mandarin, where the phonetic realization of a toneless suffix is heavily influenced by the tone of the preceding syllable but where the latter can still be considered to be realized phonetically on the syllable to which it is lexically associated [START_REF] Chen | Production of Weak Elements in Speech-Evidence from F₀ Patterns of Neutral Tone in Standard Chinese[END_REF].

Tone can also be used for marking morphological alternations. In MSEA, this is relatively rare, except in Sino-Tibetan, where morphological alternations involving tone are most abundant in Kuki-Chin (see Ozerov in preparation for an overview and a case study of Anal) and in Na-Qiangic (Evans 2008;[START_REF] Jacques | Approaching the historical phonology of three highly eroded Sino-Tibetan languages: Naxi, Na and Laze[END_REF][START_REF] Daudey | A grammar of Wadu Pumi[END_REF]. Cases of morphology conveyed solely by tone (i.e. tonal morphology proper) are much rarer than cases of conditioning of tone assignment by morphosyntax (i.e. morphotonology). In Anal (Ozerov in preparation), omission of grammatical suffixes leads to a grammatical distinction being marked only by tonal alternations on the last syllable of the stem. Interestingly, traces of the reduced suffix can consist of (i) changed tone, (ii) vowel lengthening, or (iii) both tone change and vowel lengthening.

Another example is the Burmese creaky tone, which can express possession on a restricted number of lexemes (pronouns, kinship terms and a few more) in place of the full possessive marker, also carrying creaky tone (Okell & Allott 2001: 273). Naxi (Sino-Tibetan) has cases of reduction of H-tone grammatical words to a floating H tone, whereas M-and L-tone syllables that become coalescent are reported to retain a vowel target of their own, i.e. the reduction process stops short of complete segmental ellipsis [START_REF] Michaud | Reassociated tones and coalescent syllables in Naxi (Tibeto-Burman)[END_REF].

Phrasal prosody

The phrasal prosody of MSEA languages has attracted far less systematic attention than their word-level prosody. In this section, we first review research on prosodic domains ( §3.1).

We then go over descriptions of intonational patterns and their interaction with final particles ( §3.2) and explore the role of information structure in the languages of the area ( §3.3).

Prosodic phrasing

The study of prosodic phrasing in MSEA has developed steadily in the past decade.

Research has focused on the difficulty of applying the standard Prosodic Hierarchy [START_REF] Selkirk | Phonology and Syntax: The Relation between Sound and Structure Cambridge[END_REF][START_REF] Nespor | Prosodic Phonology Dordrecht/Riverton[END_REF] to the languages of the region. While some languages, like Boro, faithfully conform to the Hierarchy (Das 2017), a number of researchers question the very existence of a universal hierarchy, especially in the Sino-Tibetan domain, and argue for emergent domains (Hildebrandt 2007: 353-376;[START_REF] Bickel | The distribution of phonological word domains: A probabilistic typology[END_REF][START_REF] Post | The phonology and grammar of Galo "words": A case study in benign disunity[END_REF][START_REF] Schiering | The prosodic word is not universal, but emergent[END_REF]Michaud 2017).

Most studies adopt a narrower scope and focus on evidence (or lack thereof) for specific osodi do ains (Phạ 00 ; Chi kova & Mi haud 009; [START_REF] Karlsson | Intonation adapts to lexical tone: the case of Kammu[END_REF][START_REF] Michaud | Information Structure in Asia: Yongning Na (Sino-Tibetan) and Vietnamese (Austroasiatic). The Oxford Handbook of Information Structure[END_REF].

For instance, the absence of segmental or suprasegmental processes in grammatical words argues against the existence of a prosodic word in Vietnamese (Schiering et To our knowledge, the issue of prosodic recursion, the embedding of a prosodic constituent within a constituent of the same type, has not yet been explored systematically in MSEA. A notable exception is Boro, a language in which a tone spreading process suggests that enclitics are parsed into a recursive prosodic word that also encompasses the prosodic word formed around its host [START_REF] Das | Tonal Alignment and Prosodic Word domains in Boro[END_REF][START_REF] Das | Tone and Intonation in Boro[END_REF].

Intonation

The study of intonation, and more specifically that of the interaction between tone and intonation, has been studied in a number of MSEA languages. Although it is still too early to reach strong conclusions, it seems that boundary tones3 can play an important role in the intonational phonology of languages with small tone inventories [START_REF] Blood | Clause and Sentence Final Particles in Cham[END_REF][START_REF] House | The phrasefinal accent in kammu: effects of tone, focus and engagement[END_REF]; The lack of categorical realization of intonation in languages with large tone inventories could be facilitated by sentence-final particles, which are a pervasive feature of most MSEA languages. These often have the same function as intonation, arguably making it redundant. In fact, [START_REF] Hyman | Tonal and non-tonal intonation in Shekgalagari. Prosodic categories: production, perception and comprehension[END_REF] have proposed to treat such particles as a part of the intonational system. However, the existence of final particles alone does not imply that intonation is not employed, either redundantly or primarily (e.g. Dryer 2013); much more work in this area is needed.

Information structure

In many MSEA languages, information structure is primarily marked by means of syntactic restructuring and overt morphological markers. The reader is referred to [START_REF] Michaud | Information Structure in Asia: Yongning Na (Sino-Tibetan) and Vietnamese (Austroasiatic). The Oxford Handbook of Information Structure[END_REF] for an overview of such markers in Yongning Na and Vietnamese. More relevant to this chapter is the prosodic marking of information structure. Although these structures have not received much attention in the languages of the area, they seem to mainly include prosodic phrasing and overt focus.

A Yongning Na example of information structure realized through prosodic phrasing is given in ( 5) In this exa le 'dog eat' is to i alized and thus o s a tone g ou se a ate from the rest of the sentence, a phrasing that is marked by the bolded tone changes (see Michaud 2017: 324-327 for detailed tone rules). Brunelle 2017) and pragmatic focus [START_REF] Jannedy | Prosodic Focus in Vietnamese[END_REF]. Results reveal that speakers can realize focus through a number of correlates of vocal effort, such as raised f 0 and intensity, increased duration, and a fuller realization of tone contours and phonation types associated to tones.

However, speakers do not need to use all these cues simultaneously, and they exhibit significant individual variation. In spontaneous speech, prosodic focus is normally accompanied by morphosyntactic focus-marking strategies.

Conclusion

In this short chapter, we have attempted to give an overview of the diverse prosodic systems of MSEA. We have argued that it is difficult to characterize the languages of the region in terms of a few stereotypical prosodic properties. The chapter also reflects the state of our current knowledge on the prosodic structures of MSEA: while their word-level prosody is wellunderstood, it is imperative that more work be conducted on their phrasal prosody, which is still ill-understood.

  (9) egiste in Wa e t og a s o the lea egiste wo d tɛ 'sweet' (le t) and b eath egiste tɛ ' ea h' (right). The clear register is characterised by sharper, more clearly defined formants; the breathy register has relatively more energy at very low frequencies and high frequency noise. The Wa register contrast applies independently of syllable-inal /h/ and /ʔ/ aking possible the set of distinct syllables in (10). (10) vowel register independent of laryngeal consonants in Wa tɛ concerns the stability of register systems, which have frequently been seen to ' est u tu e' ( u an 976) o ove to ealize a ont ast b eans o a single acoustic property. An apparently recent shift from register to a primarily pitch-based system has

  2.2). To our knowledge, these systems are restricted to Sino-Tibetan languages of the Himalayas, on the northern periphery of the area under consideration here. Analyses of other languages of SEA in terms of level tones have also been proposed (e.g.Morén & Zsiga 2006 on Thai), but such proposals are challenging to evaluate in the absence of language-internal (morpho)phonological evidence[START_REF] Clements | Do we need tone features?[END_REF].Finally, MSEA is home to a number of languages with complex tonation systems involving multiple phonetic properties. While there may be a certain amount of variation, a hallmark of such systems is the canonical co-occurrence of two or more phonetic properties. For example, three of the six tones in Northern Vietnamese are systematically realized with a laryngealized voice quality in sonorant-inal s llables ( ũ 9 ; gu n & Ed ondson 997; Michaud 2004), and perceptual research has shown that the strong glottalization of the low glottalized tone is normally sufficient for identification, to the point of largely overriding pitch cues(Brunelle

  ), a morpheme may have lexically high or low tone. Functional morphemes attached to a noun or verb stem may have no lexically specified tone, in which case their tone is derived by a process whereby high and low tones alternate such that adjacent highs or lows are avoided where possible, i.e. unless a lexically specified tone makes adjacent highs or lows inevitable. Examples of sentences with a lexically high tone ve b ste [ k] 'give' and a low tone ve b [hŋà] 'bo ow' a e given in ( ) o the right a string of verbal auxiliaries and particles are attached, and to the left of the stem a subject/object prefix is attached. Only the verb stem has lexical tone: the attached morphemes are assigned alternating high and low tones so no adjacent tones are the same. had to give ' ʔə -hŋà-l ʔ-hnì H-L-H-L 3-borrow-must-PRF ' e has had to bo ow ' In Sumtu, the dual number in verb paradigms is indicated by tone, as shown in (13). The lexi all low tone ve b [s ʔ] 'go' has ino -syllable pronominal prefixes attached. In the singular and the plural forms, these prefixes have a high tone: having lexically assigned tone, they assume the tone which is the polar opposite of the stem to which they are attached. However, the dual number is indicated by a tone change in the pronoun prefix; the low tone dual pronominal prefix provokes a dissimilatory tone change in the verb stem, so that in the dual forms the verb stem has a high tone. (13) Tone change in Myebon Sumtu dual number verb forms

  said that one ust not eat dog eat! / It is said that dog eat is so ething one ust not eat!' (Mi haud and B unelle 0 6) Vietnamese is the MSEA language in which overt focus has been studied the most systematically. Studies have been ondu ted on o e tive o us (Mi haud 005; ũ et al. 2005;

  The effect of boundary tones can also be seen in languages with large tone inventories. The clearest cases are languages in which the pitch contour of toneless particles can be predicted based on intonation, such as Thai[START_REF] Pittayaporn | Prosody of Final Particles in Thai: Interaction between Lexical Tones and Boundary Tones[END_REF], or in which an intonational contour overrides the lexical tone of discourse markers, like backchannels and repair utterances in o the n ietna ese ( ạ 0 0; 0 ) oweve the t i al s ena io in su h languages is that intonational effects are realized through a combination of various cues, such as the global pitch height and slope of the utterance, phrase-inal it h ontou and du ation ( n 967; Đỗ et al.

		boy name go study already		boy name go study already
		'Ka has gone to s hool '		' as Ka gone to s hool?'
	( ) inal bounda tones ealized on the inal in Easte n Cha (Phạ and B unelle 2014):
	registers are autosegmentally represented as H/L for convenience.
		L H	H L L L%		L H H	L L H%
	a.	a ka naw a	b.	a ka naw a

[START_REF] Karlsson | Influence of lexical tones on intonation in Kammu[END_REF] Karlsson et al. 0 ; Phạ & B unelle 0 )

In o the n Kh u a twoway tone contrast does not prevent the realization of a phrasal H tone on the rightmost edge of every prosodic phrase; the tone curves are adjusted accordingly

[START_REF] Karlsson | Intonation adapts to lexical tone: the case of Kammu[END_REF]

. A simpler example is Eastern Cham, a language in which sentence-final boundary tones concatenate with register on the final syllable, as illustrated in (14). 99 ; Luksanee anawin 99 ; gu n & Boulakia 999; Mi haud 005; ũ et al. 2006; Brunelle et al. 0 ; Mạ 0 ) It is un lea i these intonational ues whi h show g eat speaker variability, can be analyzed as categorical boundary tones in the autosegmental-metrical sense (Michaud 2005; Brunelle et al. 2012; Brunelle 2016).

  Abramson, A. S., M. K. Tiede & T. Luangthongkum. 2015. Voice Register in Mon: Acoustics and Electroglottography. Phonetica 72.237-56. Abramson, Arthur S & Theraphan Luangthongkum. 2009. A fuzzy boundary between tone languages and voice-register languages. Frontiers in Phonetics and Speech Science.149-55.

Indo-European and Dravidian languages are also spoken by sizeable language communities in Burma, Malaysia and Northeast India, but are not covered in this chapter.

Tsat, a Chamic (Austronesian) language spoken in Hainan, has a full-fledged tone system[START_REF] Maddieson | Tone in Utsat[END_REF] Pang 1993, Thurgood et al. 2015).

The term boundary tone is used as a convenient label for intonational effects that are mostly realized at the edge of intonational domains. The authors recognize a divergent range of views on whether these effects should be formalized as tones or as a different type of primitive (on this topic, see Rialland to appear).