Advances and Novel Approaches in Discrete Optimization

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section "Mathematics and Computer Science".

Deadline for manuscript submissions: closed (15 June 2020) | Viewed by 55987

Printed Edition Available!
A printed edition of this Special Issue is available here.

Special Issue Editor


E-Mail Website
Guest Editor
Faculty of Mathematics, Otto-von-Guericke-University, P.O. Box 4120, D-39016 Magdeburg, Germany
Interests: scheduling; development of exact and approximate algorithms; stability investigations; discrete optimization; scheduling with interval processing times; complex investigations for scheduling problems; train scheduling; graph theory; logistics; supply chains; packing; simulation; applications
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

We invite you to submit your latest research in the area of discrete optimization to this Special Issue, “Advances and Novel Approaches in Discrete Optimization”, in the journal Mathematics. We are looking for new and innovative approaches for exactly or approximately solving discrete optimization problems. High-quality papers are solicited to address both theoretical and practical issues in discrete optimization. Submissions are welcome presenting new theoretical results, structural investigations, new models and algorithmic approaches, as well as new applications of discrete optimization problems. Potential topics include, but are not limited to, integer programming, combinatorial optimization, graphs and networks, scheduling, logistics, and transportation.

Prof. Dr. Frank Werner
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • nonlinear and linear integer programming
  • optimization problems on graphs and networks
  • combinatorial optimization
  • scheduling
  • optimization in logistics and transport
  • robust discrete optimization
  • optimization under uncertainty
  • polyhedral combinatorics
  • complexity issues
  • branch and bound, cutting-plane methods, dynamic programming
  • approximation and randomized algorithms
  • online algorithms
  • advanced heuristics, metaheuristics, and matheuristics
  • constraint programming
  • interior point methods
  • decomposition methods

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (18 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Editorial

Jump to: Research

4 pages, 184 KiB  
Editorial
Advances and Novel Approaches in Discrete Optimization
by Frank Werner
Mathematics 2020, 8(9), 1426; https://doi.org/10.3390/math8091426 - 25 Aug 2020
Cited by 1 | Viewed by 1823
Abstract
Discrete optimization is an important area of applied mathematics which is at the intersection of several disciplines and covers both theoretical and practical aspects [...] Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)

Research

Jump to: Editorial

51 pages, 1267 KiB  
Article
Schedule Execution for Two-Machine Job-Shop to Minimize Makespan with Uncertain Processing Times
by Yuri N. Sotskov, Natalja M. Matsveichuk and Vadzim D. Hatsura
Mathematics 2020, 8(8), 1314; https://doi.org/10.3390/math8081314 - 7 Aug 2020
Cited by 6 | Viewed by 2357
Abstract
This study addresses a two-machine job-shop scheduling problem with fixed lower and upper bounds on the job processing times. An exact value of the job duration remains unknown until completing the job. The objective is to minimize a schedule length (makespan). It is [...] Read more.
This study addresses a two-machine job-shop scheduling problem with fixed lower and upper bounds on the job processing times. An exact value of the job duration remains unknown until completing the job. The objective is to minimize a schedule length (makespan). It is investigated how to best execute a schedule, if the job processing time may be equal to any real number from the given (closed) interval. Scheduling decisions consist of the off-line phase and the on-line phase of scheduling. Using the fixed lower and upper bounds on the job processing times available at the off-line phase, a scheduler may determine a minimal dominant set of schedules (minimal DS), which is based on the proven sufficient conditions for a schedule dominance. The DS optimally covers all possible realizations of the uncertain (interval) processing times, i.e., for each feasible scenario, there exists at least one optimal schedule in the minimal DS. The DS enables a scheduler to make the on-line scheduling decision, if a local information on completing some jobs becomes known. The stability approach enables a scheduler to choose optimal schedules for most feasible scenarios. The on-line scheduling algorithms have been developed with the asymptotic complexity O(n2) for n given jobs. The computational experiment shows the effectiveness of these algorithms. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Graphical abstract

16 pages, 2794 KiB  
Article
RISC Conversions for LNS Arithmetic in Embedded Systems
by Peter Drahoš, Michal Kocúr, Oto Haffner, Erik Kučera and Alena Kozáková
Mathematics 2020, 8(8), 1208; https://doi.org/10.3390/math8081208 - 22 Jul 2020
Cited by 3 | Viewed by 2083
Abstract
The paper presents an original methodology for the implementation of the Logarithmic Number System (LNS) arithmetic, which uses Reduced Instruction Set Computing (RISC). The core of the proposed method is a newly developed algorithm for conversion between LNS and the floating point (FLP) [...] Read more.
The paper presents an original methodology for the implementation of the Logarithmic Number System (LNS) arithmetic, which uses Reduced Instruction Set Computing (RISC). The core of the proposed method is a newly developed algorithm for conversion between LNS and the floating point (FLP) representations named “looping in sectors”, which brings about reduced memory consumption without a loss of accuracy. The resulting effective RISC conversions use only elementary computer operations without the need to employ multiplication, division, or other functions. Verification of the new concept and related developed algorithms for conversion between the LNS and the FLP representations was realized on Field Programmable Gate Arrays (FPGA), and the conversion accuracy was evaluated via simulation. Using the proposed method, a maximum relative conversion error of less than ±0.001% was achieved with a 22-ns delay and a total of 50 slices of FPGA consumed including memory cells. Promising applications of the proposed method are in embedded systems that are expanding into increasingly demanding applications, such as camera systems, lidars and 2D/3D image processing, neural networks, car control units, autonomous control systems that require more computing power, etc. In embedded systems for real-time control, the developed conversion algorithm can appear in two forms: as RISC conversions or as a simple RISC-based logarithmic addition. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

15 pages, 343 KiB  
Article
On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty
by Alexander A. Lazarev, Nikolay Pravdivets and Frank Werner
Mathematics 2020, 8(7), 1131; https://doi.org/10.3390/math8071131 - 10 Jul 2020
Cited by 7 | Viewed by 2732
Abstract
In this paper, we consider the single-machine scheduling problem with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both [...] Read more.
In this paper, we consider the single-machine scheduling problem with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem gives a lower bound on the optimal objective function value of the original problem, we use the optimal function value of a sub-problem of the dual problem in a branch and bound algorithm for the original single-machine scheduling problem. We present some initial computational results for instances with up to 20 jobs. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

17 pages, 4283 KiB  
Article
Packing Oblique 3D Objects
by Alexander Pankratov, Tatiana Romanova and Igor Litvinchev
Mathematics 2020, 8(7), 1130; https://doi.org/10.3390/math8071130 - 10 Jul 2020
Cited by 15 | Viewed by 4396
Abstract
Packing irregular 3D objects in a cuboid of minimum volume is considered. Each object is composed of a number of convex shapes, such as oblique and right circular cylinders, cones and truncated cones. New analytical tools are introduced to state placement constraints for [...] Read more.
Packing irregular 3D objects in a cuboid of minimum volume is considered. Each object is composed of a number of convex shapes, such as oblique and right circular cylinders, cones and truncated cones. New analytical tools are introduced to state placement constraints for oblique shapes. Using the phi-function technique, optimized packing is reduced to a nonlinear programming problem. Novel solution approach is provided and illustrated by numerical examples. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

25 pages, 11908 KiB  
Article
Optimization Methodologies and Testing on Standard Benchmark Functions of Load Frequency Control for Interconnected Multi Area Power System in Smart Grids
by Krishan Arora, Ashok Kumar, Vikram Kumar Kamboj, Deepak Prashar, Sudan Jha, Bhanu Shrestha and Gyanendra Prasad Joshi
Mathematics 2020, 8(6), 980; https://doi.org/10.3390/math8060980 - 16 Jun 2020
Cited by 37 | Viewed by 3288
Abstract
In the recent era, the need for modern smart grid system leads to the selection of optimized analysis and planning for power generation and management. Renewable sources like wind energy play a vital role to support the modern smart grid system. However, it [...] Read more.
In the recent era, the need for modern smart grid system leads to the selection of optimized analysis and planning for power generation and management. Renewable sources like wind energy play a vital role to support the modern smart grid system. However, it requires a proper commitment for scheduling of generating units, which needs proper load frequency control and unit commitment problem. In this research area, a novel methodology has been suggested, named Harris hawks optimizer (HHO), to solve the frequency constraint issues. The suggested algorithm was tested and examined for several regular benchmark functions like unimodal, multi-modal, and fixed dimension to solve the numerical optimization problem. The comparison was carried out for various existing models and simulation results demonstrate that the projected algorithm illustrates better results towards load frequency control problem of smart grid arrangement as compared with existing optimization models. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

21 pages, 1780 KiB  
Article
Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application
by Yuriy Shablya, Dmitry Kruchinin and Vladimir Kruchinin
Mathematics 2020, 8(6), 962; https://doi.org/10.3390/math8060962 - 12 Jun 2020
Cited by 11 | Viewed by 3969
Abstract
In this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one [...] Read more.
In this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one of these methods, which is based on AND/OR trees. This method is extended by using the mathematical apparatus of the theory of generating functions since it is one of the basic approaches in combinatorics (we propose to use the method of compositae for obtaining explicit expression of the coefficients of generating functions). As a result, we also apply this method and develop new ranking and unranking algorithms for the following combinatorial sets: permutations, permutations with ascents, combinations, Dyck paths with return steps, labeled Dyck paths with ascents on return steps. For each of them, we construct an AND/OR tree structure, find a bijection between the elements of the combinatorial set and the set of variants of the AND/OR tree, and develop algorithms for ranking and unranking the variants of the AND/OR tree. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

9 pages, 296 KiB  
Article
Join Products K2,3 + Cn
by Michal Staš
Mathematics 2020, 8(6), 925; https://doi.org/10.3390/math8060925 - 5 Jun 2020
Cited by 10 | Viewed by 2847
Abstract
The crossing number cr ( G ) of a graph G is the minimum number of edge crossings over all drawings of G in the plane. The main goal of the paper is to state the crossing number of the join product [...] Read more.
The crossing number cr ( G ) of a graph G is the minimum number of edge crossings over all drawings of G in the plane. The main goal of the paper is to state the crossing number of the join product K 2 , 3 + C n for the complete bipartite graph K 2 , 3 , where C n is the cycle on n vertices. In the proofs, the idea of a minimum number of crossings between two distinct configurations in the various forms of arithmetic means will be extended. Finally, adding one more edge to the graph K 2 , 3 , we also offer the crossing number of the join product of one other graph with the cycle C n . Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

16 pages, 284 KiB  
Article
A New Formulation for the Capacitated Lot Sizing Problem with Batch Ordering Allowing Shortages
by Yajaira Cardona-Valdés, Samuel Nucamendi-Guillén, Rodrigo E. Peimbert-García, Gustavo Macedo-Barragán and Eduardo Díaz-Medina
Mathematics 2020, 8(6), 878; https://doi.org/10.3390/math8060878 - 1 Jun 2020
Cited by 3 | Viewed by 2513
Abstract
This paper addresses the multi-product, multi-period capacitated lot sizing problem. In particular, this work determines the optimal lot size allowing for shortages (imposed by budget restrictions), but with a penalty cost. The developed models are well suited to the usually rather inflexible production [...] Read more.
This paper addresses the multi-product, multi-period capacitated lot sizing problem. In particular, this work determines the optimal lot size allowing for shortages (imposed by budget restrictions), but with a penalty cost. The developed models are well suited to the usually rather inflexible production resources found in retail industries. Two models are proposed based on mixed-integer formulations: (i) one that allows shortage and (ii) one that forces fulfilling the demand. Both models are implemented over test instances and a case study of a real industry. By investigating the properties of the obtained solutions, we can determine whether the shortage allowance will benefit the company. The experimental results indicate that, for the test instances, the fact of allowing shortages produces savings up to 17% in comparison with the model without shortages, whereas concerning the current situation of the company, these savings represent 33% of the total costs while preserving the revenue. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

20 pages, 1261 KiB  
Article
A Deep Learning Algorithm for the Max-Cut Problem Based on Pointer Network Structure with Supervised Learning and Reinforcement Learning Strategies
by Shenshen Gu and Yue Yang
Mathematics 2020, 8(2), 298; https://doi.org/10.3390/math8020298 - 22 Feb 2020
Cited by 17 | Viewed by 6827
Abstract
The Max-cut problem is a well-known combinatorial optimization problem, which has many real-world applications. However, the problem has been proven to be non-deterministic polynomial-hard (NP-hard), which means that exact solution algorithms are not suitable for large-scale situations, as it is too time-consuming to [...] Read more.
The Max-cut problem is a well-known combinatorial optimization problem, which has many real-world applications. However, the problem has been proven to be non-deterministic polynomial-hard (NP-hard), which means that exact solution algorithms are not suitable for large-scale situations, as it is too time-consuming to obtain a solution. Therefore, designing heuristic algorithms is a promising but challenging direction to effectively solve large-scale Max-cut problems. For this reason, we propose a unique method which combines a pointer network and two deep learning strategies (supervised learning and reinforcement learning) in this paper, in order to address this challenge. A pointer network is a sequence-to-sequence deep neural network, which can extract data features in a purely data-driven way to discover the hidden laws behind data. Combining the characteristics of the Max-cut problem, we designed the input and output mechanisms of the pointer network model, and we used supervised learning and reinforcement learning to train the model to evaluate the model performance. Through experiments, we illustrated that our model can be well applied to solve large-scale Max-cut problems. Our experimental results also revealed that the new method will further encourage broader exploration of deep neural network for large-scale combinatorial optimization problems. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

12 pages, 289 KiB  
Article
Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families
by Wenhua Li, Libo Wang, Xing Chai and Hang Yuan
Mathematics 2020, 8(2), 170; https://doi.org/10.3390/math8020170 - 1 Feb 2020
Cited by 7 | Viewed by 2110
Abstract
We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of [...] Read more.
We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = α j s j , where α j > 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + α max ) f , where f is the number of job families and α max is the maximum deterioration rate of all jobs. When m 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + α max . Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

42 pages, 565 KiB  
Article
Dynamic Restructuring Framework for Scheduling with Release Times and Due-Dates
by Nodari Vakhania
Mathematics 2019, 7(11), 1104; https://doi.org/10.3390/math7111104 - 14 Nov 2019
Cited by 5 | Viewed by 2517
Abstract
Scheduling jobs with release and due dates on a single machine is a classical strongly NP-hard combination optimization problem. It has not only immediate real-life applications but also it is effectively used for the solution of more complex multiprocessor and shop scheduling problems. [...] Read more.
Scheduling jobs with release and due dates on a single machine is a classical strongly NP-hard combination optimization problem. It has not only immediate real-life applications but also it is effectively used for the solution of more complex multiprocessor and shop scheduling problems. Here, we propose a general method that can be applied to the scheduling problems with job release times and due-dates. Based on this method, we carry out a detailed study of the single-machine scheduling problem, disclosing its useful structural properties. These properties give us more insight into the complex nature of the problem and its bottleneck feature that makes it intractable. This method also helps us to expose explicit conditions when the problem can be solved in polynomial time. In particular, we establish the complexity status of the special case of the problem in which job processing times are mutually divisible by constructing a polynomial-time algorithm that solves this setting. Apparently, this setting is a maximal polynomially solvable special case of the single-machine scheduling problem with non-arbitrary job processing times. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

29 pages, 4101 KiB  
Article
Efficient Dynamic Flow Algorithms for Evacuation Planning Problems with Partial Lane Reversal
by Urmila Pyakurel, Hari Nandan Nath, Stephan Dempe and Tanka Nath Dhamala
Mathematics 2019, 7(10), 993; https://doi.org/10.3390/math7100993 - 19 Oct 2019
Cited by 26 | Viewed by 4470
Abstract
Contraflow technique has gained a considerable focus in evacuation planning research over the past several years. In this work, we design efficient algorithms to solve the maximum, lex-maximum, earliest arrival, and quickest dynamic flow problems having constant attributes and their generalizations with partial [...] Read more.
Contraflow technique has gained a considerable focus in evacuation planning research over the past several years. In this work, we design efficient algorithms to solve the maximum, lex-maximum, earliest arrival, and quickest dynamic flow problems having constant attributes and their generalizations with partial contraflow reconfiguration in the context of evacuation planning. The partial static contraflow problems, that are foundations to the dynamic flows, are also studied. Moreover, the contraflow model with inflow-dependent transit time on arcs is introduced. A strongly polynomial time algorithm to compute approximate solution of the quickest partial contraflow problem on two terminal networks is presented, which is substantiated by numerical computations considering Kathmandu road network as an evacuation network. Our results show that the quickest time to evacuate a flow of value 100,000 units is reduced by more than 42% using the partial contraflow technique, and the difference is more with the increase in the flow value. Moreover, the technique keeps the record of the portions of the road network not used by the evacuees. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

11 pages, 241 KiB  
Article
Online Bi-Criteria Scheduling on Batch Machines with Machine Costs
by Wenhua Li, Weina Zhai and Xing Chai
Mathematics 2019, 7(10), 960; https://doi.org/10.3390/math7100960 - 13 Oct 2019
Cited by 2 | Viewed by 1929
Abstract
We consider online scheduling with bi-criteria on parallel batch machines, where the batch capacity is unbounded. In this paper, online means that jobs’ arrival is over time. The objective is to minimize the maximum machine cost subject to the makespan being at its [...] Read more.
We consider online scheduling with bi-criteria on parallel batch machines, where the batch capacity is unbounded. In this paper, online means that jobs’ arrival is over time. The objective is to minimize the maximum machine cost subject to the makespan being at its minimum. In unbounded parallel batch scheduling, a machine can process several jobs simultaneously as a batch. The processing time of a job and a batch is equal to 1. When job J j is processed on machine M i , it results cost c i j . We only consider two types of cost functions: c i j = a + c j and c i j = a · c j , where a is the fixed cost of machines and c j is the cost of job J j . The number of jobs is n and the number of machines is m. For this problem, we provide two online algorithms, which are showed to be the best possible with a competitive ratio of ( 1 + β m , n m ) , where β m is the positive root of the equation ( 1 + β m ) m + 1 = β m + 2 . Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
10 pages, 244 KiB  
Article
Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time
by Hongjun Wei, Jinjiang Yuan and Yuan Gao
Mathematics 2019, 7(9), 819; https://doi.org/10.3390/math7090819 - 5 Sep 2019
Cited by 2 | Viewed by 1757
Abstract
We consider the coordination of transportation and batching scheduling with one single vehicle for minimizing total weighted completion time. The computational complexity of the problem with batch capacity of at least 2 was posed as open in the literature. For this problem, we [...] Read more.
We consider the coordination of transportation and batching scheduling with one single vehicle for minimizing total weighted completion time. The computational complexity of the problem with batch capacity of at least 2 was posed as open in the literature. For this problem, we show the unary NP-hardness for every batch capacity at least 3 and present a polynomial-time 3-approximation algorithm when the batch capacity is at least 2. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
8 pages, 234 KiB  
Article
Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval
by Lili Zuo, Zhenxia Sun, Lingfa Lu and Liqi Zhang
Mathematics 2019, 7(8), 668; https://doi.org/10.3390/math7080668 - 26 Jul 2019
Cited by 9 | Viewed by 2538
Abstract
In this paper, we study two scheduling problems on a single machine with rejection and an operator non-availability interval. In the operator non-availability interval, no job can be started or be completed. However, a crossover job is allowed such that it can be [...] Read more.
In this paper, we study two scheduling problems on a single machine with rejection and an operator non-availability interval. In the operator non-availability interval, no job can be started or be completed. However, a crossover job is allowed such that it can be started before this interval and completed after this interval. Furthermore, we also assume that job rejection is allowed. That is, each job is either accepted and processed in-house, or is rejected by paying a rejection cost. Our task is to minimize the sum of the makespan (or the total weighted completion time) of accepted jobs and the total rejection cost of rejected jobs. For two scheduling problems with different objective functions, by borrowing the previous algorithms in the literature, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme (FPTAS), respectively. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
9 pages, 919 KiB  
Article
On Extended Adjacency Index with Respect to Acyclic, Unicyclic and Bicyclic Graphs
by Bin Yang, Vinayak V. Manjalapur, Sharanu P. Sajjan, Madhura M. Mathai and Jia-Bao Liu
Mathematics 2019, 7(7), 652; https://doi.org/10.3390/math7070652 - 20 Jul 2019
Cited by 7 | Viewed by 2876
Abstract
For a (molecular) graph G, the extended adjacency index E A ( G ) is defined as Equation (1). In this paper we introduce some graph transformations which increase or decrease the extended adjacency ( E A ) index. Also, we obtain [...] Read more.
For a (molecular) graph G, the extended adjacency index E A ( G ) is defined as Equation (1). In this paper we introduce some graph transformations which increase or decrease the extended adjacency ( E A ) index. Also, we obtain the extremal acyclic, unicyclic and bicyclic graphs with minimum and maximum of the E A index by a unified method, respectively. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

17 pages, 2565 KiB  
Article
On the Degree-Based Topological Indices of Some Derived Networks
by Haidar Ali, Muhammad Ahsan Binyamin, Muhammad Kashif Shafiq and Wei Gao
Mathematics 2019, 7(7), 612; https://doi.org/10.3390/math7070612 - 10 Jul 2019
Cited by 33 | Viewed by 3191
Abstract
There are numeric numbers that define chemical descriptors that represent the entire structure of a graph, which contain a basic chemical structure. Of these, the main factors of topological indices are such that they are related to different physical chemical properties of primary [...] Read more.
There are numeric numbers that define chemical descriptors that represent the entire structure of a graph, which contain a basic chemical structure. Of these, the main factors of topological indices are such that they are related to different physical chemical properties of primary chemical compounds. The biological activity of chemical compounds can be constructed by the help of topological indices. In theoretical chemistry, numerous chemical indices have been invented, such as the Zagreb index, the Randić index, the Wiener index, and many more. Hex-derived networks have an assortment of valuable applications in drug store, hardware, and systems administration. In this analysis, we compute the Forgotten index and Balaban index, and reclassified the Zagreb indices, A B C 4 index, and G A 5 index for the third type of hex-derived networks theoretically. Full article
(This article belongs to the Special Issue Advances and Novel Approaches in Discrete Optimization)
Show Figures

Figure 1

Back to TopTop