Nonstrict Vector Summation in Scheduling Problems
Nonstrict Vector Summation in Scheduling Problems
It is proved (by constructing an algorithm) that any finite family of vectors in the plane with sum zero and each vector having at most unit length can be nonstrictly summed within a given unbounded convex set in the plane which satisfies some conditions. The application of this result to three scheduling problems with three machines enables one to construct polynomial-time approximation algorithms for their solutions with worst- case absolute errors independent of the number of jobs.
- University of Management TISBI Russian Federation
- Sobolev Institute of Mathematics Russian Federation
vector summation, flow shops, Deterministic scheduling theory in operations research, three machines, assembly line, polynomial-time approximation algorithms, job shops
vector summation, flow shops, Deterministic scheduling theory in operations research, three machines, assembly line, polynomial-time approximation algorithms, job shops
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!