Research article Special Issues

An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints

  • The flexible job shop scheduling problem is important in many research fields such as production management and combinatorial optimization, and it contains sub-problems of machine assignment and operation sequencing. In this paper, we study a many-objective FJSP (MaOFJSP) with multiple time constraints on setup time, transportation time and delivery time, with the objective of minimizing the maximum completion time, the total workload, the workload of critical machine and penalties of earliness/tardiness. Based on the given problem, an improved ant colony optimization is proposed to solve the problem. A distributed coding approach is proposed by the problem features. Three initialization methods are proposed to improve the quality and diversity of the initial solutions. The front end of the algorithm is designed to iteratively update the machine assignment to search for different neighborhoods. Then the improved ant colony optimization is used for local search of the neighborhood. For the searched scheduling set the entropy weight method and non-dominated sorting are used for filtering. Then mutation and closeness operations are proposed to improve the diversity of the solutions. The algorithm was evaluated through experiments based on 28 benchmark instances. The experimental results show that the algorithm can effectively solve the MaOFJSP problem.

    Citation: Shaofeng Yan, Guohui Zhang, Jinghe Sun, Wenqiang Zhang. An improved ant colony optimization for solving the flexible job shop scheduling problem with multiple time constraints[J]. Mathematical Biosciences and Engineering, 2023, 20(4): 7519-7547. doi: 10.3934/mbe.2023325

    Related Papers:

    [1] Angel Rivera-Calzada, Andrés López-Perrote, Roberto Melero, Jasminka Boskovic, Hugo Muñoz-Hernández, Fabrizio Martino, Oscar Llorca . Structure and Assembly of the PI3K-like Protein Kinases (PIKKs) Revealed by Electron Microscopy. AIMS Biophysics, 2015, 2(2): 36-57. doi: 10.3934/biophy.2015.2.36
    [2] Emmanuel Reyes-Uribe, Nathalia Serna-Marquez, Eduardo Perez Salazar . DDRs: receptors that mediate adhesion, migration and invasion in breast cancer cells. AIMS Biophysics, 2015, 2(3): 303-317. doi: 10.3934/biophy.2015.3.303
    [3] Oleg A. Karpov, Gareth W. Fearnley, Gina A. Smith, Jayakanth Kankanala, Michael J. McPherson, Darren C. Tomlinson, Michael A. Harrison, Sreenivasan Ponnambalam . Receptor tyrosine kinase structure and function in health and disease. AIMS Biophysics, 2015, 2(4): 476-502. doi: 10.3934/biophy.2015.4.476
    [4] Michael J. Hamilton, Matthew D. Young, Silvia Sauer, Ernest Martinez . The interplay of long non-coding RNAs and MYC in cancer. AIMS Biophysics, 2015, 2(4): 794-809. doi: 10.3934/biophy.2015.4.794
    [5] Mikayel Ginovyan, Svetlana Hovhannisyan, Hayarpi Javrushyan, Gohar Sevoyan, Zaruhi Karabekian, Narine Zakaryan, Naira Sahakyan, Nikolay Avtandilyan . Screening revealed the strong cytotoxic activity of Alchemilla smirnovii and Hypericum alpestre ethanol extracts on different cancer cell lines. AIMS Biophysics, 2023, 10(1): 12-22. doi: 10.3934/biophy.2023002
    [6] Qiao Yi Chen, Max Costa, Hong Sun . Structure and function of histone acetyltransferase MOF. AIMS Biophysics, 2015, 2(4): 555-569. doi: 10.3934/biophy.2015.4.555
    [7] Mikayel Ginovyan, Agnieszka Bartoszek, Izabela Koss-Mikołajczyk, Barbara Kusznierewicz, Pierre Andreoletti, Mustapha Cherkaoui-Malki, Naira Sahakyan . Growth inhibition of cultured cancer cells by Ribes nigrum leaf extract. AIMS Biophysics, 2022, 9(3): 282-293. doi: 10.3934/biophy.2022024
    [8] Derrick Lonsdale, Chandler Marrs . The potential of lipid soluble thiamine in the treatment of cancer. AIMS Biophysics, 2020, 7(1): 17-26. doi: 10.3934/biophy.2020002
    [9] Audrey Lejart, Gilles Salbert, Sébastien Huet . Cytosine hydroxymethylation by TET enzymes: From the control of gene expression to the regulation of DNA repair mechanisms, and back. AIMS Biophysics, 2018, 5(3): 182-193. doi: 10.3934/biophy.2018.3.182
    [10] Larisa I. Fedoreyeva, Tatiana A. Dilovarova, Boris F. Vanyushin, Inna A. Chaban, Neonila V. Kononenko . Regulation of gene expression in Nicotiana tabacum seedlings by the MKASAA peptide through DNA methylation via the RdDM pathway. AIMS Biophysics, 2022, 9(2): 113-129. doi: 10.3934/biophy.2022011
  • The flexible job shop scheduling problem is important in many research fields such as production management and combinatorial optimization, and it contains sub-problems of machine assignment and operation sequencing. In this paper, we study a many-objective FJSP (MaOFJSP) with multiple time constraints on setup time, transportation time and delivery time, with the objective of minimizing the maximum completion time, the total workload, the workload of critical machine and penalties of earliness/tardiness. Based on the given problem, an improved ant colony optimization is proposed to solve the problem. A distributed coding approach is proposed by the problem features. Three initialization methods are proposed to improve the quality and diversity of the initial solutions. The front end of the algorithm is designed to iteratively update the machine assignment to search for different neighborhoods. Then the improved ant colony optimization is used for local search of the neighborhood. For the searched scheduling set the entropy weight method and non-dominated sorting are used for filtering. Then mutation and closeness operations are proposed to improve the diversity of the solutions. The algorithm was evaluated through experiments based on 28 benchmark instances. The experimental results show that the algorithm can effectively solve the MaOFJSP problem.



    1. Introducing Polysaccharides as Polyelectrolyte Materials

    Polysaccharides are a family of carbohydrates playing fundamental roles in many biological contexts. Their structure is made of sugar rings linked by glycosidic bonds and various side functions [1]. Glycosidic bonds can be relatively easily biodegraded via glycoside hydrolase enzymes whilst the side groups directly affect polymer charge density, hydration and chemical reactivity, also being responsible for the formation of secondary structures. In the presence of charges, polysaccharides may behave like polyelectrolytes with the peculiar ability to ionize in aqueous media. Ionization aids in the solubilization of the polyelectrolytes, further being responsible for its unique properties. Noteworthy, polyelectrolyte dissolution is not comparable to the dissolution of a simple salt, because do not produce ions i.e., cation/anion—with comparable size and independent mobility such as a salt in solution - but dissolving to yield a polyion and counter ions. In particular, polyions have mobility and hold a large number of charges in close proximity, so that individual charges are strongly attached to the macromolecular backbone, with short mobility within the domain of the macromolecular coil. The negative charges are generally represented by carboxylic groups (COO) with pKa around 3-5 or sulfate groups (SO3−) with a pKa of around 0.5-1.5 [2]. Instead, positively charged groups are ammonium groups (NH 3+) with a pKa of around 7-10 [3]. This allows to self-assembly differently charged polysaccharides (see supplementary materials—Figure 1) by interactions between the negative and positive groups and by the entropic gain associated with these associations [4]. There are two main groups of polysaccharides: cellulose and all the derivatives from plant cells (i.e., alginates), or those from animal sources—i.e., chitin from the shells of shrimp and other sea crustaceans (see supplementary materials—Figure 2).

    Figure 1. Positive and negative polyelectrolites: Chitosan and Alginate formulas.
    Figure 2. Scheme of production of chitosan and alginate from natural sources.

    1.1. Negatively charged polyelectrolyte: alginate

    Alginate is a polyanionic polysaccharide, not toxic, biocompatible, highly hydrophilic, generally used as stabilizer, viscosifier, and gelling agent in food, textile, pharmaceutical and biotechnological industries [5,6]. They are the main structural component of marine brown algae, which confer them strength and flexibility [7], but are also present in capsular components of soil bacteria as protection from desiccation and mechanical stress [8]. Alginic acid is obtained by acid extraction from algal tissue followed by neutralization with alkali and precipitation by the addition of calcium chloride or mineral acid. It is reconverted in sodium alginate through alkali treatment. Haug, et al. have elucidated the structural constitution of alginic acid by partial acid hydrolysis, showing that chemically alginate is made by block of (1-4)-linked β-D-mannuronic acid (M) and α-L-guluronic acid (G) monomers, alternate into different form of polymers. From chemical point of view, alginate is characterized by consecutive G residues (G-block), consecutive M residues (M-block) and alternating MG residues in equal proportion (MG-blocks) [9] or unequal proportion (GGM- and MMG-blocks) [10,11], depending especially upon the organism and tissue from which it is isolated as reported by Harding, et al. As other polysaccharides, alginate is a polydispersed system and its molecular weight is characterized by a broad distribution of molecular weights as confirmed by a polydispersivity index more than 1.1 [12,13].

    Smidsørdh, et al. have largely described the high affinity of alginates for alkaline multivalent cations in order Mg2+ << Ca2+ < Sr2+ < Ba2+, underlining how it selectivity increases as the content of α-L-guluronate residues into the chain, independently upon the amount of poly-mannuronate blocks [14]. This mainly influences the ionotropic gelation due to the ionic interaction of divalent cations guluronic acid blocks, thus resulting in the formation of three-dimensional network, usually described by the “egg-box” model [15,16].

    Haug, et al. focused on the correlation between the chemical structure and the physical properties of alginate. They demonstrated that solubility is influenced by many parameters, among this the pH of the solution, the ionic strength of medium and the presence of gelling ions in the solvent. Indeed, over a certain value of pH, the carboxylic acid group can be deprotonated and the alginate may be dissolved fast (see supplementary materials—Figure 3). Every alginate have own pKa value depending from the chemical composition, the concentration of alginate, and the ionic strength of the solvent gel [17]. Besides, alginic acid is not completely soluble in any solvent including water, while Na-alginate is soluble in water. Increasing the pH, the Na-alginate solutions may behave in two different ways: a rapid increase of catalysts—i.e., H+ in solution—providing the precipitation of alginic acid, or a slow increase with a formation of alginic acid. Comparing precipitation curves of alginate from different sources, again Haug, et al. demonstrated that pH induced alginate precipitation may be different as a function of the polymer molecular weight. In this context, the presence of homopolymeric blocks generally promotes the formation of crystalline regions stabilized by hydrogen bond, thus corroborating mechanisms groups of alginate precipitation [18].

    Figure 3. Mechanisms of alginate and chitosan degradation as a function of the pH conditions.

    1.1.1. Chemical modification of alginate

    Ionic crosslinking is a more simple procedure to form 3D alginate networks, by the diffusion of bivalent ions i.e., calcium, Zinc—among polymer chains. Alternatively, ions just present into the alginate network, may be released in a controlled way, as a consequence of solubility changes driven by pH variation of the microenvironment [19]. In these cases, no auxiliary molecules or catalyst are required to mediate the ions interactions among the polar groups. Starting from this approach, more complex systems such as interpenetrate or semi-interpenetrate polyelectrolytes may be fabricated to more precisely control mechanical and swelling properties [20,21,22], Since ionic crosslinking alginates have very limited stability in vivodue to ion exchange mechanisms occurring at physiological conditions—polysaccharides are also modified by chemical way to obtain polymers with improving biological properties mediated by the large extent of functional groups along their molecular chain. Several reviews have described chemical routes based on covalent crosslink to form alginate, by a classification of involved chemical groups - secondary -OH (C-2 and C-3) or -COOH (C-6) ones. In this case, different crosslinking agents may be used epichlorohydrin [18], glutaraldehyde [23], hexamethylenediisocyanate [24], adipic acid hydrazide [25], and carbodiimide strategy [26], which may variously affect mechanical and chemical properties of the ultimate alginates.

    An alternative approach to modify alginates is thought oxidation reaction on hydroxyl groups at C-2 and C-3. Oxidation via periodates leads to the formation of dialdehyde in each oxidized monomer unit by the rupture of carbon-carbon bond of vicinal glycols. So, alginate derivatives result more labile, with increased degradability, hydrophobicity and easy attachment of substituents or reductive agents by reductive amination [27,28].

    Reductive amination between dialdehyde and alkyl amine needs reducing agents like sodium borohydride (NaBH4) sodium cyanoborohydride (NaCNBH4). With this method is possible to introduce long alkyl chains to the alginates achieve new alginate-derived polymeric surfactant with amphiphilic properties. Kang, et al. synthesized a series of alginate-derived polymeric surfactants (APSs) with a linear alkyl group (C8, C12, C16) by oxidation followed by reductive amination of 2,3-dialdehydic alginate [29,30]. By this method Laurienzo, et al. prepared sodium alginate grafted with low molecular weight polyethylene glycol (PEG), a promising candidate for any application in which alginate gels with higher biocompatibility and pores dimension are required, as for gel entrapment devices and microencapsulation techniques [31].

    Hydroxyl sites of alginates can also undergo to a series of reactions like acetylation, phosphorylation, sulfation. Bræk, et al. showed that a moderate increase of degree of acetylation of alginate causes an expansion of the molecular chain whereas a higher degree of acetylation generates more flexible polymers increasing swelling ability [32]. Coleman, et al. prepared phosphorylated alginate hydrogels using a heterogeneous urea/phosphate reaction, which enhanced resistance to degradation [33]. Freman, et al. prepared sulfated alginate scaffold characterized by high blood compatibility and anticoagulant activity [34]. In addition, graft reaction of hydroxyl group of alginate may be optimized to increase swelling, metal ion uptake, flocculation and degradation times [35]. A very simple method to chemically modify alginate is the esterification of carboxylic groups, by the reaction of several alcohols and alkyl halides in presence of catalysts [36]. Yang, et al. have grafted fatty alcohols (octanol, dodecanol or hexadecanol) to form novel amphiphilic alginate esters (Alg-C8, Alg-C12 or Alg-C16), useful as protein drugs and a carrier of hydrophobic drugs [37]. Mahou, et al. have synthesized alginate-poly(ethylene glycol) hybrid microspheres, by the esterification of sodium alginate with vinyl sulfone-terminated multi-arm PEG (PEG-VS) directly into cell culture medium, for the transplantation of microencapsulated living cells [38]. Moreover, Jindal, et al. synthesized sodium alginate-cysteine conjugated by carbodiimides, obtaining thiolate residues with more efficient controlled drug release, mucoadhesiveness, swelling behavior and cohesivity [39,40]. Amidation of carboxylic groups with amine containing molecules have been alternatively proposed to form more hydrophilic derivatives for nucleus pulposus replacement in tissue engineering [41], or amphiphilic derivatives [42]. Lastly, alginate based hydrogels of alginate ca be also crosslinked by photo-irradiation, a less invasive strategy based on the controlled exposure to ultraviolet (UV) light to rapidly crosslink polymer chains in physiological conditions in situ [43].

    1.2. Positively charged polyelectrolyte: chitosan

    Chitosan is a natural polymer obtained from chitin partially deacetylation, made from alternating monomers of 2-acetamido-2-deoxy-β-D-glucopyranose (GlcNAc; A) and 2-amino-2-deoxy-β-D-glucopyranose (GlcN; D) [44]. Deacetylation can be performed in acid, alkaline condition [45] or by chitin deacetylases. In the first case, the acid condition causes not only deacetylation of acetamido-groups of chitin, but also hydrolysis of β-glycosidic linkage with a consequent severe degradation of the polysaccharide. In the second case, the drastic alkaline condition (15-20 M NaOH at 100-120 °C) is able to deacetylate the acetamido-groups no hydrolyzing the β-glycosidic linkage. Zhao, et al. characterized the existing classes of deacetylases, demonstrating that the deacetylases recognize a sequence of four GlcNAc units in the substrate, one of which undergoes deacetylation: the resulting chitosan has a more regular deacetylation pattern than a chitosan treated with NaOH [45]. Deacetylated amino groups are very electronegative and can take up a proton allowing chitosan to behave as a hydrophilic polycations, with different chemical, physical, and biological properties from chitin. For example, Deacetylation degree (DA) generally influences polarity, pH, ionic strength and, ultimately, water soluble behavior [46]. Varum, et al. have demonstrated that chitosans—generally soluble at pH below 6—becomes soluble at pH ranging from 4 to 9 for Da = 0.60, or at pH from 6 to 7.5 for lower DA (see supplementary materials—Figure 3) [47]. Moreover, molecular weight and polydispersivity index controlled by several methods as acid hydrolysis (HCl, HNO2), free radicals (H2O2, K2S2O8), radiation (UV, γ-rays), microwaves, and thermal treatment [48], may drastically affect the polymer viscosity, mainly in the presence electrolytes [49].

    Positive charge of chitosan allows forming complexes with different ions, i.e., transition metal and post-transition ions as a funtion of their selectivity Cu > Hg > Zn > Cd > Ni > Co = Ca [50] in order to obtain a non-toxic flocculent or chelating agents for the removal of heavy and reactive metals from industrial waste water [51].

    Wang, et al. focused on the pKa of chitosan with different DA and molecular weight demonstrated that a slightly decreasing from 6.51 to 6.39 is possible when MW changing from 1370 to 60 kDa, while a increasing from 6.17 to 6.51 is obtained when DA decreasing from 94.6 to 73.3% [52]. Water solubility also depends from the ionic concentration, and a salting-out effect may be observed in excess of HCl (1 M HCl), making possible to prepare the chlorhydrate form of chitosan, which is soluble in water giving an acid solution with pKa 6 ± 0.1 [49]. In this context, several studies performed by IR [53], UV [54], 1H-NMR [55], 13C-NMR [56], 15N-NMR [57] studies have been demonstrated a relevant contribution of spatial distribution of acetyl groups, inter-chain H-bonding and hydrophobic properties of acetyl groups on solubility and, ultimately, on enzymes diffusion trough the chitosan network at physiological pH, and their significant outcomes in terms of biological response.

    1.2.1. Chemical modification of chitosan

    Chitosan has two types of reactive groups, the free amino groups on deacetylated units, and two hydroxyl groups on C-3 and C-6. Sreenivas and Pai, in their review, showed all the chemical modification, via derivatization with various reagents, bearing sulfhydryl functions on the chitosan, and all the properties of thiolated chitosan included the enhanced mucoadhesiveness, cohesiveness and permeation effect [58]. Jayakumar, et al. summarized different methods of preparation of sulfated chitin and chitosan and their properties, and their recent applications in various fields such as: cardio-vascular (as blood anticoagulant and hemagglutination inhibitor), antimicrobial, adsorbing metal ions, biomedical and drug delivery [59,60]. Sashiwa, et al. reported the successful preparation of water soluble chitosan derivatives by simple N,O-acetylation in MeSO3H as solvent useful to induce a hydrophobic nature to hydrophilic chitosan backbone and prevent particle aggregation [61].

    Many chemical modifications have been studied to make the solubility and the positive charge of chitosan independent from the pH. Jayakumar, et al. introduced phosphonic acid or phosphanate onto chitosan, by reaction of phosphorylating agent onto the amino groups, obtaining phosphorylated-chitosans which are known to have enhanced chelating properties and water solubility [62,63]. Quaternization of primary amine of deacetylated glucosamine also increases the solubility of chitosan in water in a large range of pH. Rúnarsson, et al. developed a novel “one potN-selective synthesis procedure to obtain N-trimethylated chitosan chloride (TMC) [60], one of the most common partially quaternized derivative of chitosan, without secondary O-methylation. The N-trimethylation of chitosan increases the mucoadhesive properties of the polysaccharide. Several studies extensively reported by Rosenthal, et al. demonstrated that the effect of chitosan on the paracellular permeability is dependent on its positive charge, but chitosan is positively charged only at pH values lower than 6.5. To overcome chitosan’s limited effectiveness as absorption enhancer at neutral and alkaline pH values as present in the small intestine, chitosan derivatives have been developed, such as trimethyl chitosan (TMC) and Mono N-carboxymethyl chitosan (MCC), which had comparable effects on the TJs [64,65]. As widely reported by Mourya, et al. carboxymethyl chitosan (CMC) has been widely studied because of its ease of synthesis, ampholytic character and possibilities of ample of applications. The carboxymethylation can be attended through reductive alkylation or direct alkylation and the substitution can affect the hydroxyl or the amine group [66]. This modification can change not only properties such as viscosity, flocculation, chelation [67] but also biological properties as modulation of cell functioning and activities as antioxidant, antibacterial and anti-apoptotic [68]. This derivative may be properly used in sustained or controlled release drug delivery, pH responsive drug delivery, DNA delivery and as permeation enhancer too [69,71].

    An easy and common strategy to improve thermal stability, swelling ratio and mechanical strength of chitosan is the use of a crosslinker agents like glutaraldehyde, oxalic acid, formaldehyde, glyoxal and genipin [72]. Metallic anions, sulfate, citrate, and phosphate-bearing groups, such as β-glycerophosphate and tripolyphosphate (TPP), may react with Chitosans to form derivatives well tolerate and biocompatible, useful in drug delivery. The main disadvantages of ionic crosslinking concern their lacks in mechanical and chemical stability, due to a highly pH-sensitive swelling [72]. Alternatively, γ-radiation and UV-light have been used to prepare graft copolymers. Cai, et al. used 60C-γ-radiation to graft N-isopropylacrilamide to fabricate pH sensitive chitosan with good swelling properties [73]. Photo-induced grafting of polyethylenglicole (PEG) on carboxymethyl chitosan has been used to to develop a pH responsive drug delivery system [74]. Yamada, et al. lso propose the use of enzymes to synthesize chitosan with unique pH-sensitive water solubility and adhesive properties [75]. Due to their cationic functions, chitosans may be successfully used to form complexes with opposite charged polymers i.e., polyanions such as alginates or proteins—with enormous potential applications in cell encapsulation, drug delivery, and tissue engineering [76].

    2. Metabolic Activities of Polysaccharides

    In order to realize more efficient systems for drug delivery and the tissue engineering, with higher therapeutic effect and optimal targeting, stimulo-sensitive polymers have to be used. Environmental stimuli may be classified as follows:

    - Physiological stimuli such as pH, enzymatic activities, redox potential, and glucose concentration;

    - External stimuli like temperature, light, magnetic field and mechanical force [77].

    Besides, the design of stimuli responsive systems requires a more accurate control of degradation rates of polysaccharides, occurring via cleavage of the glycosidic bonds and polysaccharide depolymerization, by the fine definition of reactants concentration and synthesis temperature. Hence, it is mandatory to properly understand the mechanism of degradation of polysaccharides at physiological condition and/or in the presence of enzymatic activities.

    2.1. pH driven degradation

    The ability of some polysaccharides to react as a function of pH conditions represents an interesting way to direct the drug to a certain tissue or cellular compartment. For instance, the degradation of alginates is strongly dependent on the pH. Haug, et al. studied the degradation of alginate from Laminaria digitata at different values of pH. They demonstrated that alginate is stable only in a range of pH-values ranging from 5 to 10. Two different degradation mechanisms may be recognized: for pH less than 5, proton-catalyzed hydrolysis is predominant, while for pH more than 10, degradation occurs via β-alkoxy-elimination [78]. Timell described the acid hydrolysis of glycosidic bond through a mechanism of three steps: (a) protonation of the glycosidic oxygen to give conjugate acid; (b) heterolysis of conjugate acid forming a not reducing end group a carbonium-oxonium ion: and (c) rapid addition of water to the carbonium-oxonium ion, forming a reducing end group [79]. Not only H+ but also carbonate and phosphate ions could catalyzed β-elimination. Haug also showed as is possible identify the contribution of β-elimination reaction with a simple colorimetric thiobarbituric acid assay [80]. Esterified alginates are more predisposed to β-elimination compared with other types of alginates, because the esterification increases the electron-attracting effect of carbonyl group in C6 which increases the rate of removal of H-5 in the first step of the β-elimination reaction. Degradation can be significant even at pH values around neutrality because most brown algae contain varying amounts of phenolic compounds which are extracted together with the alginate and represent a contamination in most commercial alginates. This degradation effect of phenolic compounds belongs to the class of ORD reactions (Oxidative-Reductive Depolymerisation) [81].

    pH has a very important effect on chitosan degradation. As reported by Holme, et al. acid hydrolysis is the primary mechanism involved in chitosan degradation even if like other polysaccharides is also influenced by several degradation mechanisms [82]. Varum, et al. demonstrated that acid catalyzed not only N-acetyl linkage but also O-glycosidic linkage hydrolysis. The rate of hydrolysis of the glycosidic linkages was found to be equal to the rate of de-N-acetylation in dilute acid, while was ten times faster in concentrated acid due to different mechanism of degradation. Furthermore they demonstrated that the acid hydrolysis of glycosidic linkages depends in particularly from the DA of chitosan, in particular the degradation increases with increasing the degree of acetylation of chitosan, indeed the acid hydrolysis is specific to cleavage of A-A and A-D glycosidic linkages, because the positive charge close to the glycosidic linkage destabilizes the hydrolysis mechanism [83]. For a chitosan with medium molecular weight, DA around 0.5, ionic strength of 0.1 M and at 60 °C have been investigated about the degradation rate as a function of pH conditions from 1 to 14: the degradation is at minimum between 3 to 10. The decrease stability at pH values less than 3 is due to the acid hydrolysis of β-glycosidic-linkage and the relative increases in the degradation at low pH will be proportionally to DA. The reaction responsible for the degradation at pH higher than 10 and above could be catalyzed from alkali hydrolysis but also oxidative-reductive degradation reaction. The rate of both reactions will be expected to increase increasing pH, however chitosan is relatively stable toward alkaline degradation [84]. As previously seen, simple covalent modifications can make chitosan resistant to acid hydrolysis in the stomach, and allow to chitosan performs its mucoadhesive and absorption properties in small intestine, that is the main absorptive region of the GIT [85].

    The data suggested that acid hydrolysis and β-elimination, due to alkaline conditions, are the primary mechanisms involved in the degradation of alginate, while the chitosan degradation is mainly driven by acid hydrolysis.

    2.2. Enzymatic degradation

    In vivo, delivery systems can interact with many enzymes able to degrade them. An enzymatic activity is related to a particular compartment of organism, or the enzyme levels are up-regulated at the target site. In these cases is possible design polymeric systems that deliver drugs via specific enzymatic degradation. The enzyme-based approach is a biocompatible, but especially high sensitivity and selective method to deliver drugs: for example, the metabolic activity of colonic microflora, able to cleave glycosidic linkages of saccharides, is an attractive way for targeting drug via polysaccharides in pathological tissues (i.e., colon) [86,87].

    Alginate is naturally degraded by a class of enzymes called Alginate lyases or alginate depolymerases.

    Wong, et al. summarized all the characteristics e biological roles of alginate lyases. This enzymes(EC 4.2.2.-) have been isolated from several sources: marine algae, marine animals and bacteria, gram-negative and gram-positive soil bacteria, marine fungi and virus and other microorganisms, while is not present in human organisms. In marine organisms, Alginate lyase is degraded and metabolized by the cell wall of brown algae, rich of alginate, to obtain a source of carbon and energy. Alginate lyases are a group of enzymes which cleave the polymer chains via a β-elimination mechanism, and even if all lyases have the same mechanism of degradation, each enzyme is defined by its individual characteristics and its preference for the glycolytic bond connecting M and G monomers (see supplementary materials—Figure 4). They reported that most of the lyases have a preference for poly(M) substrates, although a few G-specific lyases have been identified. The majority of lyases have endo-cleaving activity, only few kinds have exolytic activity [88]. Gacesa proposed a three steps mechanism to elucidate the reaction that include (a) removal of negative charge on the carboxyl anion; (b)abstraction of the proton on C5 by a general base-catalysis; (c) transfer of electron from carboxyl group to form a double bond between C4 and C5, resulting in the β-elimination of the 4-O-glycosidic bond [89]. Alginate lyases usually are used to study the composition of alginate, but they are also involved into an innovative process of biofuel production [90].

    Figure 4. Enzymatic degradation mechanisms of Alginates.

    Chitosan degrading enzymes are less abundant than chitin degrading enzymes, reflecting its minor abundance in nature. Chitosan is predominantly degraded by enzymes which hydrolyze the glucosamine-glucosamine, glucosamine-N-acetyl-glucosamine, N-acetyl-glucosamine-N-acetyl-glucosamine linkage. Lysozyme and bacterial enzymes in the colon are the main enzymes involved in chitosan degradation [91]. However three human chitinases, of the GH18 family, with enzymatic activity have been identified. As reported by FunkHouser, et al., they are: di-N-acetylchitobiase, chitotriosidase and acid mammalian chitinase, all endochitinases (EC 3.2.1.14) [92].

    Moreover, lysozyme is able to hydrolyze chitin and chitosan [93], the rate of degradation is inversely related to the crystallinity, and to the chitosan degree of deacetylation. In human body lysozyme have been found in different concentration in serum (4 to 13 mg/L), tears (450 to 1230 mg/L), saliva and urine [94,95] where have an important antibacterial activity [96]. Even if human lysozyme (EC 3.2.1.17) [97] is structurally different from lysozyme usually used for in vitro test, Cohen demonstrated that have a similar activity on biodegradation of chitosan [98]. As reported in several studies in vitro and in vivo, the degrading activity of lysozyme increases with increasing chitosan Degree of Acetylation (DA), suggesting that a minimum of acetylated units had to be contained in lysozyme binding site to obtain a maximum initial degradation rates. Indeed, is largely demonstrated that lysozyme contains a hexameric binding site and hexasaccharide sequence containing 3 or more GlcNAc, while can’t act on GlcN residues or in segment with small fraction of GlcNAc [99,103]. All these is in agreement with the use of chitosan with low DA as lysozyme’s inhibitor as reported by Varum, et al. [104]. N-acetyl-beta-D-glucosaminidase or NAGase (EC 3.2.1.52), which is distributed in various tissue cells, catalyses hydrolytic release of terminal β-(1-4)-linked N-acetyl-glucosamine residues from the non-reducing ends of chito-oligosaccharides [105]. Lim, et al. used a mixture solution of lysozyme and NAGase, in vitro and in vivo, and found that in vitro degradation of chitosan was similar to in vivo, also showing a synergistic effect between the two enzymes. Chitosan is initial degraded by lysozyme to oligomers or low-molecular species, later is degraded by NAGase to monomers. Using chitosan with different DA is possible obtain carrier with different degradation time for tissue engineering application [106].

    3. Polysaccharide Degradation in Drug Delivery and Tissue Engineering

    On-demand controlled drug delivery is becoming feasible by the design of stimuli-responsive systems that recognize their microenvironment and react in a dynamic way. This approach is mainly interesting in tissue engineering due to the great possibility to finely tune bioactive molecules release to dynamically match the needs to address tissue in-growth (See Table 1 and 2). The use of polysaccharides with controlled degradation rates may assure a correct matching of growth rate of tissue in order to progressively form it in the place of the scaffold—namely porous platform with controlled architecture to promote basic cell functions (i.e., adhesion, proliferation, differentiation) [107].

    Table 1. Summary of main chitosan application fields.
    Chitosan applicationReferences
    Cosmetic[125]
    Photography[126]
    Artificially skin[127]
    Agriculture[128]
    Food and nutrition[129]
    Ophthalmology[130, 131]
    Water engineering[132]
    Drug delivery
      - Hydrogel[133]
      - Tablet[134]
      - Tablet for controlled release[135]
      - Microcapsule[136]
      - Nanocapsule[137]
      - Beades[138]
      - Transdermal system[139]
    Antibacterial agent[140]
    Blood anti-coagulants[141]
    Anti-thrombogenic and haemostatic materials[142]
    Fat trapper[143]
     | Show Table
    DownLoad: CSV
    Table 2. Summary of main Alginate application fields.
    Alginate applicationReferences
    Cosmetic[144]
    Food industry[145]
    Biofuel[146]
    Oral vaccination[147]
    Drug delivery[148]
      - Hydrogel[149]
      - Floating beads[150]
      - wound dressing[151]
    Implantation of living cells[152]
    Antihemostatic [153]
    Hypocholesterolemic[154]
    Hypoglycemic[154]
    Anti-hypertension[155]
    Anti-obesity[156]
    Antitumoral [157]
    Prophylaxy of radionuclide intoxication[158]
     | Show Table
    DownLoad: CSV

    In the last years, different polysaccharides have been used to design porous scaffolds to study tissue growth in “in vitro” three-dimensional (3D) models [108,109]. For instance, Li, et al. prepared 3D scaffold of chitosan-alginate to promote proliferation of chondrocyte cells and production of collagen type II to improve cartilage repair and regeneration [110]. More recently, chitosan-alginate scaffolds have been designed to reproduce the complex 3D microenvironment of tumor, so offering a new interesting platform for the development and study of anticancer therapeutics [111,112].

    In this context, environmental parameters such as pH, can support the degradation of the polymer matrix corroborating the activity of enzymes in vivo. In particular, pH can either trigger the release of molecules or promote the internalization of polymer nanoparticles into cell cytoplasm, thus compensating all the specific microenvironmental changes associated with alteration of specific enzymes (such as proteases, phospolipases or glycosidases) in pathological conditions such as ischemia, inflammatory diseases or cancer [113].

    As for drug delivery, smart carriers based on polysaccharides may differently work under different pH conditions, generally exerted by in vivo microenvironment, thus protecting the active principles from gastric juices or premature metabolism, to preserve the release of loaded drug until the target site [87]. Due to the reduced alginate metabolization by specific enzymes in human, it may be combined with other phases (i.e., laponite) to form hybrid nanocarriers with pH sensitivity for the sustained release of doxorubicin for cancer inhibition. Similar approaches have been also proven for the design of drug loaded capsules for the treatment of stomach diseases (pH 1.0-3.0) [114]. Alternatively, alginates have been extensively used to design drug release systems with inhibition of molecular diffusion at the gastric level (acid pH), due to the conversion of sodium alginate into insoluble alginic acid, and a rapid release of drug at intestinal level (higher pH), ascribable to the re-conversion of alginic acid into a soluble viscous alginate [115]. In order to overcome some limitations due to the pronounced burst release of alginates, other polysaccharides may be used as coating or external shell to more efficiently control drug release rates from alginate core [116,117,118]. While chitosan ionized and solubilized at strong acid conditions of the stomach, it tend to rapidly swell, forming a ionic gel at neutral pH of the intestine - thus releasing therapeutic molecules by the polymer degradation [119,120,121]. More recently, the pH sensitive behavior of chitosan has been also capitalized to design innovative anticancer drug-delivery systems. Indeed, the slight difference of pH existing between healthy tissues (7.4) and the extracellular environment of solid tumors (6.5-7.2) is one of parameters which stimulate the abnormal activity of tumor cells, providing a more rapid deficit of both nutrients and oxygen, thus shifting towards a glycolytic metabolism. In this context, chitosan nanoparticles may be capable of varying its surface charge - switching from nearly neutral to positive one - around tumor extracellular pH to promote their internalization into cell membrane with reduced toxicity, thus remarking a great potential for cancer therapy [122]. Alternatively, chitosan scaffold containing antiangiogenic agents have been successfully used in brain cancer to achieve a site-specific controlled release system in order to overcome current limitations in drug transport through the blood-brain barrier [123]. Feng, et al. prepared pH-responsive coacervate Chitosan/alginate microcapsules for oral administration of doxorubicin (DOX) with excellent low pH tolerance to enhance the stability of the alginate core in the stomach and its rapidly release in the small intestine. As the contact time between capsule surface and small intestine mucosal increases, the absorption of DOX may enhance, whereas the use of Layer By Layer structure offers the chance to deliver multiple drugs by encapsulating different drugs, separately, in the core and layers, respectively, for combined molecular therapies [124].

    4. Conclusion and Future Remarks

    The rapid evolution of biomedical application field have stimulated the research for investigation of new biocompatible materials suitable for a better control of cell/materials interaction and controlled drug release and targeting. In this context, polysaccharides have recently demonstrated to be a class of macromolecules, available from renewable sources, and characterized by a wide range of physical properties (i.e., environmental stimuli response), properly set by chemical modifications. This opens the opportunity to use polysaccharides and their derivatives to design innovative devices as “smart” delivery systems capable to release an entrapped drug in response to specific physiological stimuli, by an appropriate time and space release modalities. This will be assured by the set of network properties, finely tailored by polymer concentration, and crosslinking method (i.e., physical, chemical or both reactions) for the fabrication of semi or fully interpenetrated polymer networks able to reproduce a porous matrix suitable as scaffold for cell culture, with improved properties of molecular release. In perspective, multicomponent drug delivery systems could be developed for potential therapeutic and diagnostic applications.

    Acknowledgements

    This study was financially supported by POLIFARMA (PON02_3203241), REPAIR (PON01-02342) and NEWTON (FIRB-RBAP11BYNP).

    Conflict of Interest

    The authors declare no conflict of interest.



    [1] P. Brucker, R. Schlie, Job-shop scheduling with multi-purpose machines, Computing, 45 (1990), 369–375. https://doi.org/10.1007/BF02238804 doi: 10.1007/BF02238804
    [2] H. Zhang, G. Xu, R. Pan, H. Ge, A novel heuristic method for the energy-efficient flexible job-shop scheduling problem with sequence-dependent set-up and transportation time, Eng. Optim., 54 (2022), 1646–1667. https://doi.org/10.1080/0305215X.2021.1949007 doi: 10.1080/0305215X.2021.1949007
    [3] X. Shao, W. Liu, Q. Liu, C. Zhang, Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem, Int. J. Adv. Manuf. Technol., 67 (2013), 2885–2901. https://doi.org/10.1007/s00170-012-4701-3 doi: 10.1007/s00170-012-4701-3
    [4] G. Zhang, X. Shao, P. Li, L. Gao, An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Comput. Ind. Eng., 56 (2009), 1309–1318. https://doi.org/10.1016/j.cie.2008.07.021 doi: 10.1016/j.cie.2008.07.021
    [5] F. M. Defersha, D. Obimuyiwa, A. D. Yimer, Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem, Comput. Ind. Eng., 171 (2022), 108487. https://doi.org/10.1016/j.cie.2022.108487 doi: 10.1016/j.cie.2022.108487
    [6] D. Kress, D. Müller, J. Nossack, A worker constrained flexible job shop scheduling problem with sequence-dependent setup times, OR Spectrum, 41 (2019), 179–217. https://doi.org/10.1007/s00291-018-0537-z doi: 10.1007/s00291-018-0537-z
    [7] M. Li, D. Lei, An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times, Eng. Appl. Artif. Intell., 103 (2021), 104307. https://doi.org/10.1016/j.engappai.2021.104307 doi: 10.1016/j.engappai.2021.104307
    [8] Y. Wang, Q. Zhu, A hybrid genetic algorithm for flexible job shop scheduling problem with sequence-dependent setup times and job lag times, IEEE Access, 9 (2021), 104864–104873. https://doi.org/10.1109/ACCESS.2021.3096007 doi: 10.1109/ACCESS.2021.3096007
    [9] Y. Du, J. Li, C. Luo, L. Meng, A hybrid estimation of distribution algorithm for distributed flexible job shop scheduling with crane transportations, Swarm Evol. Comput., 62 (2021), 100861. https://doi.org/10.1016/j.swevo.2021.100861 doi: 10.1016/j.swevo.2021.100861
    [10] J. Q. Li, Y. Du, K. Z. Gao, P. Y. Duan, D. W. Gong, Q. K. Pan, et al., A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem, IEEE Trans. Autom. Sci. Eng., 19 (2021), 2153–2170. https://doi.org/10.1109/TASE.2021.3062979 doi: 10.1109/TASE.2021.3062979
    [11] W. Ren, Y. Yan, Y. Hu, Y. Guan, Joint optimisation for dynamic flexible job-shop scheduling problem with transportation time and resource constraints, Int. J. Prod. Res., 60 (2022), 5675–5696. https://doi.org/10.1080/00207543.2021.1968526 doi: 10.1080/00207543.2021.1968526
    [12] J. Yan, Z. Liu, C. Zhang, T. Zhang, Y. Zhang, C. Yang, Research on flexible job shop scheduling under finite transportation conditions for digital twin workshop, Rob. Comput. Integr. Manuf., 72 (2021), 102198. https://doi.org/10.1016/j.rcim.2021.102198 doi: 10.1016/j.rcim.2021.102198
    [13] J. Li, J. Deng, C. Li, Y. Han, J. Tian, B. Zhang, et al., An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times, Knowl.-Based Syst., 200 (2020), 106032. https://doi.org/10.1016/j.knosys.2020.106032 doi: 10.1016/j.knosys.2020.106032
    [14] X. Wu, X. Liu, N. Zhao, An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem, Memet. Comput., 11 (2019), 335–355. https://doi.org/10.1007/s12293-018-00278-7 doi: 10.1007/s12293-018-00278-7
    [15] G. Zhang, Y. Hu, J. Sun, W. Zhang, An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints, Swarm Evol. Comput., 54 (2020), 100664. https://doi.org/10.1016/j.swevo.2020.100664 doi: 10.1016/j.swevo.2020.100664
    [16] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ, IEEE Trans. Evol. Comput., 6 (2002), 182–197. https://doi.org/10.1109/4235.996017 doi: 10.1109/4235.996017
    [17] R. Chen, B. Yang, S. Li, S. Wang, A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem, Comput. Ind. Eng., 149 (2020), 106778. https://doi.org/10.1016/j.cie.2020.106778 doi: 10.1016/j.cie.2020.106778
    [18] X. Li, L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, Int. J. Prod. Econ., 174 (2016), 93–110. https://doi.org/10.1016/j.ijpe.2016.01.016 doi: 10.1016/j.ijpe.2016.01.016
    [19] G. Zhang, L. Gao, Y. Shi, An effective genetic algorithm for the flexible job-shop scheduling problem, Expert Syst. Appl., 38 (2011), 3563–3573. https://doi.org/10.1016/j.eswa.2010.08.145 doi: 10.1016/j.eswa.2010.08.145
    [20] L. Wang, J. Cai, M. Li, Z. Liu, Flexible job shop scheduling problem using an improved ant colony optimization, Sci. Program., 2017 (2017), 9016303. https://doi.org/10.1155/2017/9016303 doi: 10.1155/2017/9016303
    [21] H. Ding, X. Gu, Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem, Comput. Oper. Res., 121 (2020), 104951. https://doi.org/10.1016/j.cor.2020.104951 doi: 10.1016/j.cor.2020.104951
    [22] F. M. Defersha, D. Obimuyiwa, A. D. Yimer, Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem, Comput. Ind. Eng., 171 (2022), 108487. https://doi.org/10.1016/j.cie.2022.108487 doi: 10.1016/j.cie.2022.108487
    [23] G. Zhang, X. Lu, X. Liu, L. Zhang, S. Wei, W. Zhang, An effective two-stage algorithm based on convolutional neural network for the bi-objective flexible job shop scheduling problem with machine breakdown, Expert Syst. Appl., 203 (2022), 117460. https://doi.org/10.1016/j.eswa.2022.117460 doi: 10.1016/j.eswa.2022.117460
    [24] T. Jiang, H. Zhu, G. Deng, Improved African buffalo optimization algorithm for the green flexible job shop scheduling problem considering energy consumption, J. Intell. Fuzzy Syst., 38 (2020), 4573–4589. https://doi.org/10.3233/JIFS-191370 doi: 10.3233/JIFS-191370
    [25] H. Zhu, T. Jiang, Y. Wang, Discrete african buffalo optimization algorithm for the low-carbon flexible job shop scheduling problem, J. Adv. Manuf. Syst., 19 (2020), 837–854. https://doi.org/10.1142/S0219686720500390 doi: 10.1142/S0219686720500390
    [26] T. Jiang, C. Zhang, Q. M. Sun, Green job shop scheduling problem with discrete whale optimization algorithm, IEEE Access, 7 (2019), 43153–43166. https://doi.org/10.1109/ACCESS.2019.2908200 doi: 10.1109/ACCESS.2019.2908200
    [27] T. Jiang, C. Zhang, H. Zhu, J. Gu, G. Deng, et al., Energy-efficient scheduling for a job shop using an improved whale optimization algorithm, Mathematics, 6 (2018), 220. https://doi.org/10.3390/math6110220 doi: 10.3390/math6110220
    [28] P. Brandimarte, Routing and scheduling in a flexible job shop by tabu search, Ann. Oper. Res., 41 (1993), 157–183. https://doi.org/10.1007/BF02023073 doi: 10.1007/BF02023073
    [29] S. Dauzère-Pérès, J. Paulli, An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Ann. Oper. Res., 70 (1997), 281–306. https://doi.org/10.1023/A:1018930406487 doi: 10.1023/A:1018930406487
    [30] E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3 (1999), 257–271. https://doi.org/10.1109/4235.797969 doi: 10.1109/4235.797969
    [31] D. C. Montgomery, R. H. Myers, W. H. Carter Jr, G. G. Vining, The hierarchy principle in designed industrial experiments, Qual. Reliab. Eng. Int., 21 (2005), 197–201. https://doi.org/10.1002/qre.615 doi: 10.1002/qre.615
    [32] M. Yuan, Y. Li, L. Zhang, F. Pei, Research on intelligent workshop resource scheduling method based on improved NSGA-Ⅱ algorithm, Rob. Comput. Integr. Manuf., 71 (2021), 102141. https://doi.org/10.1016/j.rcim.2021.102141 doi: 10.1016/j.rcim.2021.102141
  • Reader Comments
  • © 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3042) PDF downloads(226) Cited by(10)

Article outline

Figures and Tables

Figures(17)  /  Tables(9)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog