Two-stage no-wait scheduling models with setup and removal times separated

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Incorporating voltage/reactive representation to short-term generation scheduling models

This paper proposes a methodology to incorporate voltage/reactive representation to Short Term Generation Scheduling (STGS) models, which is based on active/reactive decoupling characteristics of power systems. In such approach STGS is decoupled in both Active (AGS) and Reactive (RGS) Generation Scheduling models. AGS model establishes an initial active generation scheduling through a traditional dispatch model. The scheduling proposed by AGS model is evaluated from the voltage/reactive points of view, through the proposed RGS model. RGS is formulated as a sequence of T nonlinear OPF problems, solved separately but taking into account load tracking between consecutive time intervals. This approach considerably reduces computational effort to perform the reactive analysis of the RGS problem as a whole. When necessary, RGS model is capable to propose active generation redispatches, such that critical reactive problems (in which all reactive variables have been insufficient to control the reactive problems) can be overcome. The formulation and solution methodology proposed are evaluated in the IEEE30 system in two case studies. These studies show that the methodology is robust enough to incorporate reactive aspects to STGS problem.

Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Integrated component scheduling models for chip shooter machines

This paper focuses on minimizing printed circuit board (PCB) assembly time for a chipshootermachine, which has a movable feeder carrier holding components, a movable X–Y table carrying a PCB, and a rotary turret with multiple assembly heads. The assembly time of the machine depends on two inter-related optimization problems: the component sequencing problem and the feeder arrangement problem. Nevertheless, they were often regarded as two individual problems and solved separately. This paper proposes two complete mathematical models for the integrated problem of the machine. The models are verified by two commercial packages. Finally, a hybrid genetic algorithm previously developed by the authors is presented to solve the model. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total assembly time.

An interactive planning and scheduling framework for optimising pits-to-crushers operations

In this paper, an interactive planning and scheduling framework are proposed for optimising operations from pits to crushers in ore mining industry. Series of theoretical and practical operations research techniques are investigated to improve the overall efficiency of mining systems due to the facts that mining managers need to tackle optimisation problems within different horizons and with different levels of detail. Under this framework, mine design planning,mine production sequencing and mine transportation scheduling models are integrated and interacted within a whole optimisation system. The proposed integrated framework could be used by mining industry for reducing equipment costs, improving the production efficiency and maximising the net present value.

Scheduling Flows with Unknown Sizes: Approximate Analysis

Previous studies have shown that giving preferential treatment to short jobs helps reduce the average system response time, especially when the job size distribution possesses the heavy-tailed property. Since it has been shown that the TCP flow length distribution also has the same property, it is natural to let short TCP flows enjoy better service inside the network. Analyzing such discriminatory system requires modification to traditional job scheduling models since usually network traffic managers do not have detailed knowledge about individual flows such as their lengths. The Multi-Level (ML) queue, proposed by Kleinrock, can b e used to characterize such system. In an ML queueing system, the priority of a flow is reduced as the flow stays longer. We present an approximate analysis of the ML queueing system to obtain a closed-form solution of the average system response time function for general flow size distributions. We show that the response time of short flows can be significantly reduced without penalizing long flows.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Pre-emptive scheduling problems with controllable processing times

We consider a range of single machine and identical parallel machine pre-emptive scheduling models with controllable processing times. For each model we study a single criterion problem to minimize the compression cost of the processing times subject to the constraint that all due dates should be met. We demonstrate that each single criterion problem can be formulated in terms of minimizing a linear function over a polymatroid, and this justifies the greedy approach to its solution. A unified technique allows us to develop fast algorithms for solving both single criterion problems and bicriteria counterparts.

Fifty years of scheduling: a survey of milestones

Scheduling has become a major field within operational research with several hundred publications appearing each year. This paper explores the historical development of the subject since the mid-1950s when the landmark publications started to appear. A discussion of the main topics of scheduling research for the past five decades is provided, highlighting the key contributions that helped shape the subject. The main topics covered in the respective decades are combinatorial analysis, branch and bound, computational complexity and classification, approximate solution algorithms and enhanced scheduling models.

Scheduling and Platforming Trains at Busy Complex Stations

We consider the problem of train planning or scheduling for large, busy, complex train stations, which are common in Europe and elsewhere, though not in North America. We develop the constraints and objectives for this problem, but these are too computationally complex to solve by standard combinatorial search or integer programming methods. Also, the problem is somewhat political in nature, that is, it does not have a clear objective function because it involves multiple train operators with conflicting interests. We therefore develop scheduling heuristics analogous to those successfully adopted by train planners using ''manual'' methods. We tested the model and algorithms by applying to a typical large station that exhibits most of the complexities found in practice. The results compare well with those found by traditional methods, and take account of cost and preference trade-offs not handled by those methods. With successive refinements, the algorithm eventually took only a few seconds to run, the time depending on the version of the algorithm and the scheduling problem. The scheduling models and algorithms developed and tested here can be used on their own, or as key components for a more general system for train scheduling for a rail line or network.Train scheduling for a busy station includes ensuring that there are no conflicts between several hundred trains per day going in and out of the station on intersecting paths from multiple in-lines and out-lines to multiple platforms, while ensuring that each train is allowed at least its minimum required headways, dwell time, turnaround time and trip time. This has to be done while minimizing (costs of) deviations from desired times, platforms or lines, allowing for conflicts due to through-platforms, dead-end platforms, multiple sub-platforms, and possible constraints due to infrastructure, safety or business policy.

Developing protocols for nursery based scheduling trials

Most existing crop scheduling models are cultivar specific and are developed using academic resources. As such they rarely meet the particular needs of a grower. A series of protocols have been created to generate effective schedules for a changing product range using data generated on site at a commercial nursery. A screening programme has been developed to help determine a cultivar's photoperiod sensitivity and vernalisation requirement. Experimental conditions were obtained using a cold store facility set to 5degreesC and photoperiod cloches. Eight and 16 hour photoperiod treatments were achieved at low cost by growing plants in cloches of opaque plastic with a motorised rolling screen. Natural light conditions were extended where necessary using a high pressure sodium lamp. Batches of plants were grown according to different schedules based on these treatments. The screening programme found Coreopsis grandiflora 'Flying Saucers' to be a long day plant. Data to form the basis of graphical tracks was taken using variations on commercial schedules. The work provides a nursery based approach to the continuous improvement of crop scheduling practises.

Strategies to model scheduling decisions to plan the soft drink production process

In this paper we present a mixed integer model that integrates lot sizing and lot scheduling decisions for the production planning of a soft drink company. The main contribution of the paper is to present a model that differ from others in the literature for the constraints related to the scheduling decisions. The proposed strategy is compared to other strategies presented in the literature.

Data-Aware Scheduling in Datacenters

Datacenters have emerged as the dominant form of computing infrastructure over the last two decades. The tremendous increase in the requirements of data analysis has led to a proportional increase in power consumption and datacenters are now one of the fastest growing electricity consumers in the United States. Another rising concern is the loss of throughput due to network congestion. Scheduling models that do not explicitly account for data placement may lead to a transfer of large amounts of data over the network causing unacceptable delays. In this dissertation, we study different scheduling models that are inspired by the dual objectives of minimizing energy costs and network congestion in a datacenter. As datacenters are equipped to handle peak workloads, the average server utilization in most datacenters is very low. As a result, one can achieve huge energy savings by selectively shutting down machines when demand is low. In this dissertation, we introduce the network-aware machine activation problem to find a schedule that simultaneously minimizes the number of machines necessary and the congestion incurred in the network. Our model significantly generalizes well-studied combinatorial optimization problems such as hard-capacitated hypergraph covering and is thus strongly NP-hard. As a result, we focus on finding good approximation algorithms. Data-parallel computation frameworks such as MapReduce have popularized the design of applications that require a large amount of communication between different machines. Efficient scheduling of these communication demands is essential to guarantee efficient execution of the different applications. In the second part of the thesis, we study the approximability of the co-flow scheduling problem that has been recently introduced to capture these application-level demands. Finally, we also study the question, "In what order should one process jobs?'' Often, precedence constraints specify a partial order over the set of jobs and the objective is to find suitable schedules that satisfy the partial order. However, in the presence of hard deadline constraints, it may be impossible to find a schedule that satisfies all precedence constraints. In this thesis we formalize different variants of job scheduling with soft precedence constraints and conduct the first systematic study of these problems.