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 77
- Downloads 0
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...
The Art and Science of Modeling Decision-Making Under Severe Uncertainty
For obvious reasons, models for decision-making under severe uncertainty are austere. Simply put, there is precious little to work with under these conditions. This fact highlights the great importance of utilizing in su...
Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
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 excl...
Analogous Forecasting of Products with a Short Life Cycle
Managing a supply chain for products with a short life cycle, like fashion apparel, high-tech, personal computers, toys, CD’s etc., is challenging for many companies (Fisher and Raman, 1999). Because the life cycles of t...
Optimizing Modular Machining Line Design Problem with Mixed Activation Mode of Machining Units
A modular transfer line designing problem is investigated. The problem is to find the best subset of modules (machining units) from a given set and to assign them to different stations so that technological constraints a...