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" [...]


  •   Payday Loans In Florida. This is a permit to the world of pleasure and the lasting sex. Cialis Super Active online is a drug, the quality level of which is determined by its action speed.