Optimization problems in operations management: Applications in multi-period decision making, telecommunications and scheduling.

摘要

Optimization plays a key role in industrial applications. The problems investigated in this research span multiple industries in Production Operations Management, Scheduling and Telecommunications. Most of the optimization problems encountered are NP-hard and therefore difficult to solve. We provide below a brief description of the results obtained for the specific problems considered in this study.; In the first problem discussed in Chapters two and three, we present a structural and computational investigation of a new class of weak forecast horizons---minimal forecast horizons under the assumption that future demands are integer multiples of a positive real number. Apart from being appropriate in most practical instances, the discreteness assumption offers a significant reduction in the length of a minimal forecast horizon over the one using the classical notion of continuous future demands. We provide several conditions under which a discrete-demand forecast horizon is also a continuous-demand forecast horizon. We also show that the increase in the cost resulting from using a discrete minimal forecast horizon instead of the classical minimal forecast horizon is modest.; In Chapter four, we consider the problem of traffic grooming in all-optical networks with the objective of throughput maximization. We present an integer programming formulation which addresses this objective while constraining the number of optical transceivers at each node, the link load, and the capacity of each lightpath. Based on the structural properties of the problem we develop an heuristic algorithm based on a column generation technique. The algorithm is easy to implement, requires a modest amount of CPU time and provides high quality solutions. To ascertain the quality of solutions obtained by our column generation based algorithm, we present an alternative formulation which allows us to develop an upper bound using a Lagrangian relaxation technique. An extensive computational study is presented to justify our claims.; The final problem discussed in Chapter five of this study is a two-stage blocking flow-shop scheduling problem with a material handling constraint. We develop heuristic algorithms and a meta-heuristic search method to solve this problem. Such problems are common in production system design, service facilities design, or specialty jobs such as petrochemical processing. The absence of intermediate buffers between the stages here causes the blocking of jobs when downstream machines are occupied. The objective is to minimize the makespan. We show that this problem is unary NP-hard. We then explore the special structural features of this problem and develop two problem-specific solution construction heuristics for different job processing time scenarios. We show that these heuristics can speedup solution evolution rate by providing good starting points for a genetic algorithm, particularly when the problem is large and computational efficiency is paramount.