Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
Journal Title: Decision Making in Manufacturing and Services - Year 2017, Vol 11, Issue 1
Abstract
In the paper we consider the problem of scheduling of unit-length jobs on 3 or 4 uniform parallel machines to minimize schedule length or total completion time. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a bipartite graph of bounded degree. The edges of the graph correspond to pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that under some conditions imposed on machine speeds and the structure of incompatibility graph our problem can be solved to optimality in polynomial time. Theoretical considerations are accompanied by computer experiments with some particular model of scheduling.
Authors and Affiliations
Szymon Duraj, Paweł Kopeć, Marek Kubale, Tytus Pikies
Keywords
Related Articles
- EP ID EP420091
- DOI 10.7494/dmms.2017.11.1-2.53
- Views 90
- Downloads 0
Corrigendum to ”Extended Model Formulation of the Proportional Lot-Sizing and Scheduling Problem with Lost Demand Costs”
Amendment to Decision Making in Manufacturing and Services, vol. 5 (1–2), 2011, pp. 49–56
On the Non-Symmetric Nash and Kalai-Smorodinsky Bargaining Solutions
Recently in some negotiation application areas the usual assumption that the negotiators are symmetric has been relaxed. In particular, weights have been introduced to the Nash Bargaining Solution to reflect the differe...
A Utility Function to Solve Approximate Linear Equations for Decision Making
Suppose there are a number of decision variables linearly related to a set of outcome variables. There are at least as many outcome variables as the number of decision variables since all decisions are outcomes by themse...
BPMN – A Logical Model and Property Analysis
Business Process Modeling Notation has become a powerful and widely accepted visual language for modeling business processes. Despite its expressive power and high usability, a weak point of BPMN is the lack of formal se...
Scheduling Problems with Learning and Ageing Effects: A Survey
In recent years, many papers concerning scheduling problems with simultaneous learning and ageing effects were published. In this paper, the state of the art of research concerning these problems is presented. In order t...