I am working on a program that will render timetables for workers (contractors) with available jobs in the area so that they can choose which jobs to do. The jobs are made by people in the community. I would like the jobs shown to as many workers as possible to increase the chance it is fulfilled, but under some constraints:
- the job can only be shown to a worker if it fits inside one of the workers' availability time blocks (the data is organized by blocks of time in which the workers are available to work).
- there can be no overlaps of jobs in the schedule (multiple jobs during the same time shown to the same worker).
- would like to minimize travel distance and time between consecutive jobs
- need each job to be shown to at least (some threshold say 20/30% of workers) so it will still be taken even if it doesn't fit as well in the optimization as some of the other jobs.
So the final product would be potential schedules for workers to select jobs from when he/she logs on to the service.
At first I was thinking of using the Hungarian Algorithm but this is a many-to-many assignment problem. My second approach was using some kind of binary linear optimization where each variable is a worker-job pair (1 if the job is shown on the worker's schedule, 0 if not) but I'm not sure how to implement the "no overlap" constraint and solving it would require the algorithm to look at every possible job arrangement for each worker to optimize time and distance which to me seems very inefficient.
I would like the algorithm to rerun as more jobs or more workers are added to the service so run time is an issue. Any ideas or suggestions? I am developing the program in Python so any useful modules/libraries would be helpful as well. Thank you!