On-Line Scheduling to Minimize Average Completion Time Revisited

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

Computational study of a cutting plane algorithm for University Course Timetabling

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 with general completion costs

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

The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions

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

A hybrid genetic algorithm for the job shop scheduling problem

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

Parallel GRASP with path-relinking for job shop scheduling

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

Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem

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

Linear time approximation scheme for the multiprocessor open shop problem

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

A 3/2-Approximation algorithm for two-machine flow-shop sequencing subject to release dates

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

Geometrical Heuristics for Multiprocessor Flowshop Scheduling with Uniform Machines at Each Stage

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