Decision support for unrelated parallel machine scheduling with discrete controllable processing times

• A scheduling problem involving discrete controllable processing times is considered.
• The objectives are to minimize some scheduling criteria.
• We develop polynomial time algorithms for the considered problems.
• We further consider the NP-hard problem of the makespan case.
• An integer programming and a heuristic are presented to solve the NP-hard problem.

In a manufacturing or service system, the actual processing time of a job can be controlled by the amount of an indivisible resource allocated, such as workers or auxiliary facilities. In this paper, we consider unrelated parallel-machine scheduling problems with discrete controllable processing times. The processing time of a job is discretely controllable by the allocation of indivisible resources. The planner must make decisions on whether or how to allocate resources to jobs during the scheduling horizon to optimize the performance measures. The objective is to minimize the total cost including the cost measured by a standard criterion and the total processing cost. We first consider three scheduling criterions: the total completion time, the total machine load, and the total earliness and tardiness penalties. If the number of machines and the number of possible processing times are fixed, we develop polynomial time algorithms for the considered problems. We then consider the minimization problem of the makespan cost plus the total processing cost and present an integer programming method and a heuristic method to solve the studied problem.

Figure optionsDownload as PowerPoint slide