Minimal Resources for Fixed and Variable Job Schedules

摘要: We treat the following problem: There are n jobs with given processing times and an interval for each job's starting time. Each job must be processed, without interruption, on any one of unlimited set identical machines. A machine may process job, but no more than at point in want to find time such that number machines required all is minimal. In addition, assignment found. If every has a fixed point, problem well-known as special case Dilworth's problem. term it schedule FSP. When variable, referred variable VSP, which known exact solution procedure exists. introduce problems by reviewing previous methods offer approximate solving VSP based entropy principle informational smoothing. then formulate pure integer programming provide algorithm. This algorithm examines sequence feasibility capacitated transportation splitting elimination side constraints. Our computational experience demonstrates utility approach.