Something like this might be possible, I have changed the jobs to async methods and I keep track of them being resolved or not.

This code does not check for errors within the job or for circular dependencies.

Output of the script:

b done
a done
c done
e done
done

Code:

const runTasks = async tasks => {
  const taskArray = Object.entries(tasks)
  const resolved = {}

  while (taskArray.length) {
    const tasksToExecute = []
    for (const task of taskArray) {
      const dependencies = task[1].dependencies || []
      if (dependencies.length === 0 || dependencies.every(dependency => resolved[dependency] || false)) {
        tasksToExecute.push(task)
      }
    }

    await Promise.all(tasksToExecute.map(t => t[1].job()))
    tasksToExecute.forEach(t => {
      resolved[t[0]] = true
      taskArray.splice(taskArray.indexOf(t[0]), 1)
    })
  }
}

const tasks = {
  a: {
    job: async function () {
      return new Promise(resolve => {
        setTimeout(() => {
          console.log("a done")
          resolve()
        }, 500)
      })
    },
  },
  c: {
    job: async function () {
      return new Promise(resolve => {
        setTimeout(() => {
          console.log("c done")
          resolve()
        }, 200)
      })
    },
    dependencies: ["a", "b"],
  },
  b: {
    job: async function () {
      return new Promise(resolve => {
        setTimeout(() => {
          console.log("b done")
          resolve()
        }, 100)
      })
    },
    dependencies: [],
  },
  e: {
    job: async function () {
      return new Promise(resolve => {
        setTimeout(() => {
          console.log("e done")
          resolve()
        }, 200)
      })
    },
    dependencies: ["c", "b"],
  },
}

runTasks(tasks).then(r => console.log("done"))

A simple recursive dependencies evaluation with caching of results will do. Use Promise.all to wait for all dependencies:

function runTasks(tasks) {
  const promises = {};
  function runTask(name) {
    const {dependencies, job} = tasks[name];
    return promises[name] ??= Promise.all(dependencies.map(runTask)).then(job);
  }
  return Promise.all(Object.keys(tasks).map(runTask));
}

Maybe use Promise.allSettled instead of Promise.all in the final return statement.

If you need to detect circular dependencies, you can use

…
  const circular = Promise.reject(new Error("circular dependency"));
  circular.catch(() => { /* ignore */ }); // prevent unhandled rejection
  function runTask(name) {
    const {dependencies, job} = tasks[name];
    if (promises[name] != null) return promises[name];
    promises[name] = circular;
    return promises[name] = Promise.all(dependencies.map(runTask)).then(job);
  }
…

You can start parallel promises which can be started.

1. Start all independent task first which has no dependencies
2. After completing independent tasks store in map/set
3. Then filter a new set of tasks using the complete set repeat steps.

const wait = (ms, task) =>
  new Promise((resolve) =>
    setTimeout(() => {
      console.log(`${task} done`);
      resolve();
    }, ms)
  );

const tasks = {
  a: {
    job: () => wait(500, "A"),
    dependencies: [],
  },
  c: {
    job: () => wait(500, "C"),
    dependencies: [],
  },
  d: {
    job: () => wait(500, "D"),
    dependencies: ["a", "c"],
  },
  e: {
    job: () => wait(500, "E"),
    dependencies: ["a", "d"],
  },
};

const run = async () => {
  const completed = new Set();
  const keys = Object.keys(tasks);
  const runTasks = async (pendingTasks) => {
    const promises = pendingTasks.map((key) => tasks[key].job());
    await Promise.all(promises);
    pendingTasks.forEach((key) => completed.add(key));
  };

  const runner = async () => {
    const pendingTasks = keys.filter((key) => {
      if (!completed.has(key)) {
        const { dependencies } = tasks[key];
        return dependencies.every((dependency) => completed.has(dependency));
      }
      return false;
    });
    if (pendingTasks.length !== 0) {
      await runTasks(pendingTasks);
      return runner();
    }
  };

  await runner();
};

run();