Affordable Access

Publisher Website

On a pair of job-machine assignment problems with two stages

Authors
Journal
Computers & Operations Research
0305-0548
Publisher
Elsevier
Publication Date
Volume
37
Issue
2
Identifiers
DOI: 10.1016/j.cor.2009.05.009
Keywords
  • Scheduling
  • Combinatorial Analysis
  • Allocation
  • Assignment Problem
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract We consider two assignment problems in which a number of jobs are assigned to the same number of machines that operate in parallel, but in two stages. They are known as the ‘2-stage time minimizing assignment problem’ and the ‘bi-level time minimizing assignment problem’. These problems have the following characteristics in common: • Each of the machines processes one job (non-preemptively, without help of other machines). • The job-machine assignments are partitioned into two successive stages of parallel processing. • The objective is to minimize the makespan, the sum of the primary and the secondary completion time. Both problems can be solved by (a series of) assignment problems. We improve the related computational complexities by applying reoptimization. Under some conditions a quadratic complexity is derived. We introduce a parameter weighing the relative importance of the primary and the secondary cost per time unit. The parametric problems can be solved, for all parameter values simultaneously, within the same reduced time complexity bounds. Scope and purpose As it is often important to solve problems quickly, it is essential to reduce the computational complexity of available algorithms, as far as possible. We consider two problems which arise when parallel scheduling is done in two successive stages; they can be tackled by solving a series of linear assignment problems. We show that they can be solved more efficiently, using properties of the classical linear assignment problem. In practice, the cost per time unit in the two stages need not be equal. A parameter controlling the ratio between these costs defines a parametric version of each problem. The algorithms of reduced time complexity can be extended to these parametric problem versions.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Two due date assignment problems in scheduling a s...

on Operations Research Letters Jan 01, 2006

An assignment-based lower bound for a class of two...

on Computers & Operations Researc...

Two-machine flow shop scheduling problems with no-...

on Operations Research Letters Jan 01, 2005

Two due date assignment problems with position-dep...

on Computers & Industrial Enginee... Jan 01, 2011
More articles like this..