کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141581 957029 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The bipartite margin shop and maximum red matchings free of blue–red alternating cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
The bipartite margin shop and maximum red matchings free of blue–red alternating cycles
چکیده انگلیسی

The margin shop arises as a model of margining investment portfolios in a batch, a mandatory end-of-day risk management operation for any prime brokerage firm. The margin-shop scheduling problem is the extension of the preemptive flow-shop scheduling problem where precedence constraints can be introduced between preempted parts of jobs. This paper is devoted to the bipartite case which is equivalent to the problem of finding a maximum red matching that is free of blue–red alternating cycles in a complete bipartite graph with blue and red edges. It is also equivalent to the version of the jump-number problem for bipartite posets where jumps inside only one part should be counted. We show that the unit-time bipartite margin-shop scheduling problem is NP-hard but can be solved in polynomial time if the precedence graph is of degree at most two or a forest.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 3, August 2009, Pages 299–309
نویسندگان
, , ,