Scheduling under Uncertainties: On-line Algorithms, Cooperative Games, and Manufacturing Outsourcing

Scheduling has become a major field of the operational research discipline. Lots of scheduling models as well as algorithms have been proposed. Meanwhile, scheduling has applications in various practical problems, including, for example, manufacturing and service, compiler optimization and parallel computing. However, the vast majority of real-life problems are full of uncertainties, such as the uncertainty of future events, the lack of information among the participants and so on. Thus, scheduling under uncertainties is a very meaningful yet challenging direction of research. In this thesis, we will study the scheduling problems under uncertain environments. Both algorithmic design on scheduling models and its applications on manufacturing will be studied. Specifically, we will focus our research on online scheduling and stochastic online scheduling. We will also consider and investigate a complicated outsourcing problem arising from the manufacturing industry. With the idea of cooperative game, we derive strategies for manufacturers to improve their profits in their outsourcing operations.;This thesis consists of the following four parts, each of which investigates a specific problem on algorithmic scheduling or its application on manufacturing.;Chapter 2 studies an online uniform machine scheduling problem, where the processing time of jobs are not known until they are released. The objective is to minimize the total weighted completion time of all jobs. We present a deterministic online scheduling policy and show that its performance guarantee is only related to the number of machines and the ratio between the largest machine's speed and the total machines' speeds.;Chapter 3 considers the stochastic online version of the uniform machine scheduling problem. Different from the problem considered in Chapter 2, we can only know the expected processing time of any job at its release time, instead of the exact processing time. Our objective is to minimize the total expected weighted completion time. We examine the two cases corresponding to whether preemption is allowed or not. We develop algorithms and derive their competitive ratios.;Chapter 4 considers such a problem: A group of manufacturers outsource jobs to a single third-party, who owns a specialized facility needed to process these jobs. The third-party announces the time slots available on her facility and the associated prices. Manufacturers reserve, on a first-come-first-choose basis, time slots that they desire to utilize. Each manufacturer books chunks of facility time and sequences his jobs over the time slots booked, so as to minimize his booking and work-in-progress costs. We present some policies for manufacturers to book time slots and schedule his jobs. We investigate the issue of the third-party serving as a coordinator to create a win-win solution to all. We propose a model based on a cooperative game and devise a saving sharing scheme that is in the core. Moreover, we also investigate the honesty issue(some information is private for a manufacturer) in the cooperation. We design truth-telling mechanisms so that any player is unable to gain by purposely reporting false job data, i.e., revealing truthful information is a dominant strategy for each manufacturer. Besides, we obtain a group incentive mechanism, which can prevent any group of self-interested manufacturers from forming a coalition to lie together.;Chapter 5 considers another manufacturing outsourcing problem, which is similar as that of Chapter 4. Differently, each manufacturer just knows the expected processing time of jobs, instead of the exact processing times, when he decides his booking decision on the third-party facility. We derive the optimal policies for manufacturers to book time slots and sequence jobs over time slots booked. Moreover, we consider the cooperation among manufacturers by formulating it as a cooperative game. We construct a core allocation scheme based on the core vector derived from a Permutation Game.;The scheduling environments we have studied are complicated as they involve uncertainties such as online information, stochastic information, and incomplete information. Although the problems considered in this thesis are mainly about manufacturing, the scheduling models, properties, and algorithms we have developed are applicable to a wide variety of situations.