Well-known problems in Computer Science

Scheduling problems

  • Job-shop scheduling problem (JSP)
  • Open-shop scheduling problem (OSP)
  • Permutation flow shop problem (PFSP)
  • Single machine total tardiness problem (SMTTP)
  • Single machine total weighted tardiness problem (SMTWTP)
  • Resource-constrained project scheduling problem (RCPSP)
  • Group-shop scheduling problem (GSP)
  • Single-machine total tardiness problem with sequence dependent setup times (SMTTPDST)
  • Multistage Flowshop Scheduling Problem (MFSP) with sequence dependent setup/changeover times

Vehicle routing problems

  • Capacitated vehicle routing problem (CVRP)
  • Multi-depot vehicle routing problem (MDVRP)
  • Period vehicle routing problem (PVRP)
  • Split delivery vehicle routing problem (SDVRP)
  • Stochastic vehicle routing problem (SVRP)
  • Vehicle routing problem with pick-up and delivery (VRPPD)
  • Vehicle routing problem with time windows (VRPTW)
  • Time Dependent Vehicle Routing Problem with Time Windows (TDVRPTW)
  • Vehicle Routing Problem with Time Windows and Multiple Service Workers (VRPTWMS)

Assignment problems

  • Quadratic assignment problem (QAP)
  • Generalized assignment problem (GAP)
  • Frequency assignment problem (FAP)
  • Redundancy allocation problem (RAP)

Set problems

  • Set covering problem(SCP)
  • Set partition problem (SPP)
  • Weight constrained graph tree partition problem (WCGTPP)
  • Arc-weighted l-cardinality tree problem (AWlCTP)
  • Multiple knapsack problem (MKP)
  • Maximum independent set problem (MIS)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s