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 110
- Downloads 0
Neighbourhood Properties in Some Single Processor Scheduling Problem with Variable Efficiency and Additional Resources
In the paper, we consider a problem of scheduling a set of tasks on a single processor. Each task must be preprocessed before it can be started on a processor. The efficiency of preprocessing is variable, i.e., the rate...
Risks and implications for decision making processes associated with existing design codes or their non-existence
Buckling phenomenon is a perplexing and unresolved issue in many safety critical structures, and it has been heavily regulated. The paper highlights the risks to decision making processes due to growing tendencies of eli...
Competitive location under proportional choice: 1-suboptimal points on networks
This paper is concerned with a competitive or voting location problem on networks under a proportional choice rule that has previously been introduced by Bauer et al. (1993). We refine a discretization result of the auth...
A multi-criteria optimization approach to modeling negotiation process
The paper presents a multi-criteria optimization approach to modeling negotiation process. The negotiation process is modeled as a special multi-criteria problem. The method for finding solutions is the interactive selec...
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...