Order Preserving Allocation Of Jobs To Two Non-Identical Parallel Machines: A Solvable Case Of The Maximum Cut Problem

Autor:	Robert L. Papineau, Rene Rochette, Sankaran Lakshminarayan, Ram Lakshmanan
Rok vydání:	1979
Předmět:	Constraint (information theory) Mathematical optimization Order (business) Maximum cut Signal Processing Class (philosophy) Mean flow Algorithm Graph Computer Science Applications Information Systems Mathematics
Zdroj:	INFOR: Information Systems and Operational Research. 17:230-241
ISSN:	1916-0615 0315-5986
Popis:	In this paper we consider the problem of minimizing the mean flow time of jobs to be processed on two non-identical parallel machines. The jobs have a predetermined order, perhaps reflecting their order of arrival and each job has a known processing time (which depends on the machine). The problem is 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. It is shown that the problem can be formulated as finding a maximum cut on a structured graph. An efficient procedure for finding this cut is developed and a class of graphs on which the maximum cut problem can be solved efficiently is identified.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::4e67318ef66041cfe0b98ee67ab7766e https://doi.org/10.1080/03155986.1979.11731736 Zobrazit plný text záznamu Plný text ve formátu PDF