your company is hired to do n different jobs. Jobs have durations t1,…,tn (in ho
ID: 3777858 • Letter: Y
Question
your company is hired to do n different jobs. Jobs have durations t1,…,tn (in hours), can be done independently and all have the same deadline in 10 working days. You need to hire people to do the jobs; every hired person can work 8 hours per day. In order to save money your company wants to hire as few people as possible, but just enough to complete all jobs. You have been given a task to hire people and assign jobs to them.
Represent this problem as an algorithmic problem. What is this algorithmic problem? Is it possible to solve it in a polynomial time? What algorithms for this problem do you know?
Explanation / Answer
Parallel machine model
In scheduling problem for task assignment there can be efforts to tackle with two main issues:
1) Assigning jobs/task to the worker.
2) And processing that jobs/task at the machine.
The assignment problem concerns with the assignment of task to the worker and also the allocation of the available worker assigning to the each station to the total cost and consider the variation of work load on the worker while solving the assignment problem and additional variables of worker for solving assignment problem is also taken into account .
Notation or indices is given below:-
j, k: index of task(1.......n).
w: index of worker(1........m).
n: number of tasks.
m: number of workers.
Ct: cycle time.
dj,w: worker cost of worker w process task j.
tj,w: processing time of jth task for wth worker.
Decision Variable Xi,j ={0 otherwise 1 task j assign to station i.
Yi,j={0 otherwise 1 worker is assign
Mathematical Model Minimize the total worker cost.
Min dt=m i=1m j=s,I m w=1 dj,w yt,w…………………equ (1).
m i=1 xi,j=1 for all i task j must be assigned to only one station........................................................................equ(2). m i=1 yt,,w=1 for all i only one worker can be allocated to station ...................................................................equ(3).
Yes it is possible to solve it in polynomial time.
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.