I want to schedule tasks with Constraints (similar to the job shop scheduling problem) and thought I could use something like the Microsoft Solver Foundation (I need to use C#). But as far as I know you can only solve problems by finding the optimal maximal or minimal which takes way to long. I need an approximation so the scheduling is not optimal (as good as possible) concerning the total time but all the Constraints are fulfilled. Any ideas how to approach this problem?
I would suggest you using Z3 solver. It provides you C# API. Basically, it is a SMT solver, which searches for 'good enough' solution with respect to given constraints. It could be rather difficult to define your problem in SMTLIB language.
If it's too hard for you, look at Minizinc or Clingo solvers - just generate problem formulation as a text file, run a solver as a separate process from your C# code, parse solution back from output text file.
EDIT
If you want to minimize a length of a schedule, you can try the following approach. Let's assume that there is a schedule of length K. Is your planning problem satisfiable under this assumption? Let's call a solver to find this out! Generate several problems with different K's and run the solver iteratively. Use binary search to reduce the number of trials.