Tuesday, 16:15 - 16:40 h, Room: H 3021


Andreas S. Schulz
The joint replenishment problem and the problem of clustering frequency-constrained maintenance jobs are integer-factorization hard

Coauthor: Claudio Telha Cornejo


We present a new connection between certain sequencing problems
involving the coordination of activities and the problem of integer factorization. We use this connection to derive hardness results for three well-known problems in operations management whose computational complexity has been open for more than two decades:

  • The joint replenishment problem with general integer policies.
  • The joint replenishment problem with correction factor.
  • The problem of finding an optimal clustering of frequency-constrained maintenance jobs.
    Our hardness results imply that no polynomial-time algorithm exists for either problem, unless integer factorization is solvable in polynomial time.


    Talk 3 of the invited session Tue.3.H 3021
    "New insights for old problems" [...]
    Cluster 2
    "Combinatorial optimization" [...]


  •   The majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.