Category: Research Paper

Hanyu Gu, Hue Chi Lam , Yakov Zinder
School of Mathematical and Physical Sciences, University of Technology Sydney,
PO Box 123, Broadway, NSW 2007, Australia

Abstract

This study addresses the scheduling problem where every job requires several types of resources. At every point in time, the capacity of resources is limited. When necessary, the capacity can be increased at a cost. Each job has a due date, and the processing times of jobs are random variables with a known probability distribution. The considered problem is to determine a schedule that minimises the total cost, which consists of the cost incurred due to the violation of resource limits and the total tardiness of jobs. A genetic algorithm enhanced by local search is proposed. The sample average approximation method is used to construct a confidence interval for the optimality gap of the obtained solutions. Computational study on the application of the sample average approximation method and genetic algorithm is presented. It is revealed that the proposed method is capable of providing high-quality solutions to large instances in a reasonable time.

Gregory Z. Gutin a, Philip R. Neary b,∗ , Anders Yeo c,d

• a Computer Science Department, Royal Holloway University of London, United Kingdom
• b Economics Department, Royal Holloway University of London, United Kingdom
• c IMADA, University of Southern Denmark, Denmark
• d Department of Mathematics, University of Johannesburg, South Afric

Last time we encountered the stable marriage problem for the first time: given a set of n “men” and n “women” (where each one has a preference ranking of all the others), is it always possible to specify a matching between the two sides such that every man is paired to exactly one woman, and the matching is stable (in the formal sense defined last lecture)? Initially, we studied the stable roommates problem and found that in that related problem, stable matchings are not guaranteed to exist. Must that negative result carry over to the stable marriage problem? As it turns out, it does not. To understand why and to answer many of our fundamental questions about the stable marriage problem, we turn now to one of the great algorithms of the 20th century.