We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith’s ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. Citation Working Paper 4435-03, Sloan … Read more
In this paper we describe a successful case-study where a Branch-and-Cut algorithm yields the \lq\lq optimal” solution of a real-world timetabling problem of University courses \emph{(University Course Timetabling problem)}. The problem is formulated as a \emph{Set Packing problem} with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing … Read more
Scheduling a sequence of tasks – in the acceptation of finding the execution times – is not a trivial problem when the optimization criterion is irregular as for instance in earliness-tardiness problems. This paper presents an efficient Dynamic Programming algorithm to solve the problem with general cost functions depending on the end time of the … Read more
It is with the aim of solving scheduling problems with irregular cost functions that this paper focuses on the continuous assignment problem. It consists in partitioning a d dimensional region into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximisation of … Read more
This paper presents a hybrid genetic algorithm for the Job Shop Scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a … Read more
In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … Read more
In this paper we consider the labor constrained scheduling problem (LCSP), in which a set of jobs to be processed is subject to precedence and labor requirement constraints. Each job has a specified processing time and a labor requirements profile, which typically varies as the job is processed. Given the amount of labor available at … Read more
For the $r$-stage open shop problem with identical parallel machines at each stage and the minimum makespan criterion, an approximation scheme is constructed with running time $O(nrm + C(m,\eps))$ , where $n$ is the number of jobs, $m$ is the total number of machines, and $C(m,\eps)$ is a function independent of $n$. Citation Discrete Appl. … Read more
The two-machine flow shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best known approximation algorithms are those of Potts (1985) with a worst-case performance ratio of 5/3 and running time $O(n^3 \log n)$, and a polynomial time approximation … Read more
We consider the multi-stage multiprocessor flowshop scheduling problem with uniform machines at each stage and the minimum makespan objective. Using a vector summation technique, three polynomial-time heuristics are developed with absolute worst-case performance guarantees. As a direct corollary, in the special case of the ordinary flowshop problem we come to the best approximation algorithms (both … Read more