Order-Preserving Allocation of Jobs to Two Machines

Authors

Shailesh J. Mehta
R. Chandrasekaran
Hamilton Emmons

Document Type

Report

Publication Date

1-1-1973

Abstract

In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.

Keywords

Operations research, Dynamic programming, Mathematical optimization, Industrial engineering, Algorithms, Queueing theory, Production scheduling

Publication Title

Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University

Issue

Technical memorandum no. 287

Rights

This work is in the public domain and may be freely downloaded for personal or academic use

Recommended Citation

Mehta, Shailesh J.; Chandrasekaran, R.; and Emmons, Hamilton, "Order-Preserving Allocation of Jobs to Two Machines" (1973). Research Reports from the Department of Operations. 409.
https://commons.case.edu/wsom-ops-reports/409