Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.12.008 Byline: Dvir Shabtay, Moshe Kaspi Keywords: Scheduling; Parallel machine scheduling; Resource allocation; Equivalent load method; Computational complexity Abstract: We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n.sup.2) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time. Author Affiliation: Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel Article History: Received 30 November 2001; Accepted 13 December 2004

We study a robotic three-machine flow-shop scheduling problem, in which n identical jobs are to be processed and the objective is to minimize the makespan. After the job’s completion on either the first or the second machine it is transferred by a robot to the next (consecutive) machine in the shop. A single robot is available for transferring the jobs. We show that the problem can be solved by decomposing it into a set of sub-problems, and by providing a robot schedule to each sub-problem that yields a makespan value which matches the lower bound value. [ABSTRACT FROM AUTHOR]

Abstract: We extend the classical linear assignment problem to the case where the cost of assigning agent to task is a multiplication of task ’s cost parameter by a cost function of agent . The cost function of agent is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is -hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations. [Copyright &y& Elsevier]

Abstract: We study bicriteria problems of minimizing maximum tardiness and total due date assignment cost in various scheduling environments. We assume that each job can be assigned a different due date without any restriction, and that each due date assignment cost is a non-decreasing function of the quoted due date. We settle the complexity of most of the problems studied by either proving that they are -hard or finding a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems. [Copyright &y& Elsevier]

Abstract: In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field. [Copyright &y& Elsevier]