In this paper, we address a university-timetabling problem and present a methodology that relies on Benders’ partitioning for its solution. This partitioning results from the special nature of the ...underlying integer programming formulation for this problem. We have used our methodology to schedule courses offered by the College of Engineering as well as to those offered university-wide at Virginia Tech. The results clearly depict an improvement in the quality of course schedules obtained by our methodology over those currently used, when the performance of a timetable is measured by the total distance traveled by the faculty members from their offices in respective departments to the classrooms, where the courses are offered.
Lot streaming is the process of splitting a production lot into sublots, and then, scheduling the sublots in an overlapping fashion on the machines. In this paper, we present a polynomial-time ...procedure for determining the number of sublots of a single-lot, multiple-machine flow shop lot-streaming problem in order to minimize a unified cost-based objective function that comprises criteria pertaining to makespan, mean flow time, work-in-process, sublot-attached setup and transfer times. An experimental investigation on the performance of this solution procedure shows its efficacy in generating near-optimal solutions. Results on the relative impact of the weights (marginal costs), used in the unified cost function (corresponding to different measures) on the number of sublots obtained, are also presented.
In this paper, we address the problem of loading non-intermixable products in a vehicle consisting of compartments of different sizes. The demands of the products are different but uniform over time. ...The objective is to meet product demands and minimize setup rate (that is, the number of deliveries per unit time). Two approaches, namely, dynamic and static, are investigated and their performances are compared with each other. In the dynamic approach, deliveries are made in several discrete periods and, then, repeated in a cyclic fashion. In each of these deliveries, the allocation of products to compartments can be different. The static approach, on the other hand, assumes a continuous time scale and determines a single assignment of products to compartments that maximizes the time in which the product demands are fully satisfied by this single delivery. The comparison between the two approaches shows that the dynamic approach is superior to the static approach when a discrete time scale is considered. However, even when the discrete time scale constraint is relaxed, the dynamic approach still provides better results for relatively long cycle times.
We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply ...an exponential subset of certain relaxed Dantzig–Fulkerson–Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.
In this paper, we consider the lot-streaming problem of sequencing a set of batches, to be processed in equal sublots, in a flow-shop, so as to minimize makespan. A new heuristic procedure, called ...the bottleneck minimal idleness heuristic, is developed. Results of an experimental study are presented. It is shown that the proposed procedure generates solutions that are very close to the optimal solutions, and that the solutions generated are better than those obtained by using the fast insertion heuristic, considered to be a good heuristic for solving the flow-shop scheduling problem, when applied to the problem on hand.
In this paper, we present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a ...variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.
Lot streaming is the process of splitting a production lot into sublots, and then scheduling the sublots in overlapping fashion on the machines, in order to improve the overall performance of the ...production system. Simulation-based and industry-based reports have confirmed that substantial benefits are possible via lot streaming. In this paper, we present, for the first time, analytical results pertaining to the potential benefits of lot streaming in flow-shop systems. The results are developed using three common performance measures. These measures are (a) lakespan (i.e., the total completion time of all the lots), (b) mean flow time, and (c) average WIP level. For each, an expression of the ratio of the measure under lot streaming to the measure without lot streaming is developed. These expressions can be used to evaluate the benefits of lot streaming under certain operating conditions. It is further shown that, in special extreme cases, these expressions purely depend upon the problem parameters (i.e., the number of machines, the number of lots, the lot-sizes, etc.)
In this paper, we address a scheduling problem belonging to a two-stage assembly system that can also be viewed as a mass customization system. The first stage of this system consists of a set of ...subassembly machines, each of which produces a component type. These components are then transferred in sublots to Stage 2, where they are assembled into finished products. Stage 2 consists of multiple parallel machines. Each of these machines represents an assembly facility devoted to a product type. We represent this configuration as a m+n system, where there are m parallel machines at Stage 1 and n parallel machines at Stage 2. Lot-attached and sublot-attached setups, and transfer times/costs are encountered on the machines at both the stages. We assume that the subassemblies are transferred in equal-sized sublots to Stage 2. Given a number of lots (jobs), the problem is to determine the number of sublots to use for each lot and the sequence in which to process the lots. We consider two different objective functions, namely, minimize makespan, and minimize the total cost incurred. In view of the fact that both of these problems are NP-hard, we develop two column generation-based heuristic methods and show their efficacy over direct solution of the mixed integer programming formulations of the underlying problems. In fact, the results of our computational investigation on the use of these methods on large-sized problems reveal attainment of almost optimal solutions within a few seconds of CPU time. We also present some managerial insights.
This article addresses an integrated lot-sizing and scheduling problem that arises in the primary manufacturing phase of a pharmaceutical supply chain. Multiple pharmaceutical ingredients and their ...intermediate products are to be scheduled on parallel and capacitated bays for production in batches. Sequence-dependent setup times and costs are incurred when cleaning a bay during changeovers between different product families. The problem also contains a high multiplicity asymmetric traveling salesman-type of substructure because of sequence-dependent setups and special restrictions. Mixed-integer programming formulations are proposed for this problem and several valid inequalities are developed to tighten the model. A column generation method along with a decomposition scheme and an advanced-start solution are designed to efficiently derive good solutions to this highly complex problem. A computational investigation is performed, based on instances that closely follow a real-life application, and it demonstrates the efficacy of the proposed solution approach.
PDF