## 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