•We put forward a novel cost-oriented line balancing problem.•Several properties and special cases of the problem are studied.•We design a memetic algorithm that hybridises these properties with a ...genetic algorithm.•Computational experiments highlight the contributions of each component to the quality of the proposed method.
In order to minimize costs, manufacturing companies have been relying on assembly lines for the mass production of commodity goods. Among other issues, the successful operation of an assembly line requires balancing work among the stations of the line in order to maximize its efficiency, a problem known in the literature as the assembly line balancing problem, ALBP.
In this work, we consider an ALBP in which task assignment and equipment decisions are jointly considered, a problem that has been denoted as the robotic ALBP. Moreover, we focus on the case in which equipment has different costs, leading to a cost-oriented formulation. In order to solve the problem, which we denote as the cost-oriented robotic assembly line balancing problem, cRALBP, a hybrid metaheuristic is proposed. The metaheuristic embeds results obtained for two special cases of the problem within a genetic algorithm in order to obtain a memetic algorithm, applicable to the general problem. An extensive computational experiment shows the advantages of the hybrid approach and how each of the components of the algorithm contributes to the overall ability of the method to obtain good solutions.
We consider a non-preemptive single machine scheduling problem for a non-negative penalty function
f
, where an optimal schedule satisfies the left-shifted property, i.e. in any optimal sequence all ...executions happen without idle time with a starting time
t
0
≥
0
. For this problem, every job
j
has a priority weight
w
j
and a processing time
p
j
, and the goal is to find an order on the given jobs that minimizes
∑
w
j
f
(
C
j
)
, where
C
j
is the completion time of job
j
. This paper explores local dominance properties, which provide a powerful theoretical tool to better describe the structure of optimal solutions by identifying rules that at least one optimal solution must satisfy. We propose a novel approach, which allows to prove that the number of sequences that respect the local dominance property among three jobs is only two, not three, reducing the search space from
n
! to
n
!
/
3
⌈
n
/
3
⌉
schedules. In addition, we define some non-trivial cases for the problem with a strictly convex penalty function that admits an optimal schedule, where the jobs are ordered in non-increasing weight. Finally, we provide some insights into three future research directions based on our results (i) to reduce the number of steps required by an exact exponential algorithm to solve the problem, (ii) to incorporate the dominance properties as valid inequalities in a mathematical formulation to speed up implicit enumeration methods, and (iii) to show the computational complexity of the problem of minimizing the sum of weighted mean squared deviation of the completion times with respect to a common due date for jobs with arbitrary weights, whose status is still open.
•The balanced dispatching problem in passengers transport services on demand is shown.•Five easy-to-implement online algorithms based on a theoretical analysis are proposed.•We study the instances ...where all requested transport services could be performed.•Complexity computational and a mixed integer quadratic program model are provided.•The results show the algorithms efficiency in term of solutions and running times.
In the passengers’ transport services on demand, such as taxi services, a dispatching solution determines the service quality level and the incomes received by both drivers and the transport company. In the last years, related work has been mainly focused on improving the service quality. However, the drivers’ incomes balancing is still a challenge, especially for emerging economies. To address this situation, we introduce the balanced dispatching problem in passengers transport services (BDP-PTS) on demand, which seeks a dispatching solution that aims to minimize the variance of the incomes per unit of working time among the drivers. We propose five easy-to-implement online dispatching algorithms, which rely on dispatching rules obtained from the variance analysis and explore the performance measures for a dispatching solution provided by them. Those algorithms consider the BDP-PTS under an offline scenario, where all the information is revealed beforehand, and the maximum number of solicited transport services is performed. We are focused on a specific set of instances, called complete, which admit at least a feasible solution where all requested transport services are performed. Consequently, we prove the NP-completeness in the strong sense of the BDP-PTS under an offline scenario for these instances, and formulate a mixed integer quadratic programming (MIQP) model to solve it. This complexity computation status implies that no polynomial or pseudo time algorithms exist for solving it, unless P = NP, involving an important quantity of running time and memory resources to model and to resolve it in an empirical computation. Finally, computational experiments are carried out to compare the proposed online dispatching algorithms and the MIQP model on datasets of real complete instances from a Chilean transport company. The obtained results show that the proposed online dispatching algorithm based on the dispatching rule, called SRV, is able to reduce more efficiently the income dispersion among drivers within reduced running times, assigning over a 98% of total solicited transport service and allowing a practical implementation into an automated dispatching system on a basic hardware infrastructure, as it is the case of the transport companies in developing countries.
Over the past fifty years the population of the world has doubled, while resources as water have become increasingly scarce. In particular, water consumption has far exceeded the available of this ...resource in some regions of the world. In order to address the above problem, the possibility of reusing grey water by installing wastewater treatment plants could be a suitable alternative for several developing countries. This paper seeks to find the best configuration for these facilities in Chile by considering the economic and environmental aspects conjoint to the social dimension. The problem is modeled as a multi-objective optimization including: minimizing costs, minimizing environmental impact, maximizing phosphorus extraction from wastewater and maximizing the number of workers to be required with the goal of analyzing the sustainability of the system. To find the Pareto frontiers of multi-objective problem, a resolution framework based on an adaptation of elitist non-dominated sorting genetic algorithm (NSGA-II) is provided for the problem. From the obtained results, the non-dominated solutions and a compromise solution are computed, reporting configuration alternatives that integrate the three sustainability dimensions, the economic, the environmental and the social as objectives for the design for a sustainable system of wastewater treatment plants.
Scheduling with a processing time oracle Dufossé, Fanny; Dürr, Christoph; Nadal, Noël ...
Applied Mathematical Modelling,
April 2022, 2022-04-00, 20220401, 2022-04, Volume:
104
Journal Article
Peer reviewed
Open access
•Scheduling jobs on a single machine with the objective of minimizing the average completion time.•Processing times are uncertain and can be long or short.•A processing time oracle can be called to ...learn the precise processing time.•Performance is measured by means of the competitive ratio.•Optimal algorithms are provided both for the adaptative and non adaptive models.
In this paper we study a single machine scheduling problem with the objective of minimizing the sum of completion times. Each of the given jobs is either short or long. However the processing times are initially hidden to the algorithm, but can be tested. This is done by executing a processing time oracle, which reveals the processing time of a given job. Each test occupies a time unit in the schedule, therefore the algorithm must decide for which jobs it will call the processing time oracle. The objective value of the resulting schedule is compared with the objective value of an optimal schedule, which is computed using full information. The resulting competitive ratio measures the price of hidden processing times, and the goal is to design an algorithm with minimal competitive ratio. Two models are studied in this paper. In the non-adaptive model, the algorithm needs to decide beforehand which jobs to test, and which jobs to execute untested. However in the adaptive model, the algorithm can make these decisions adaptively depending on the outcomes of the job tests. In both models we provide optimal polynomial time algorithms following a two-phase strategy, which consist of a first phase where jobs are tested, and a second phase where jobs are executed obliviously. Experiments give strong evidence that optimal algorithms have this structure. Proving this property is left as an open problem.
Global population growth and rising living standards are increasing apparel consumption. Consequently, the consumption of resources and the generation of textile waste are increasing exponentially. ...For instance, according to the World Bank, Chile has increased textile imports by 500% in the last 20 years, even though the population has only increased by 26%. This textile import increase has resulted in the clothing desert that has been seen recently in northern Chile because most of the textiles at the end of their useful life will be disposed of in landfills or open dumps. This evidences the urgency of more efficient technologies that reduce the consumption of resources and that value waste on the way to a circular and sustainable economy. Since the textile recycling industry and environmental impact studies are currently in their nascent stages in Chile, the objective of this article is to explore the potential environmental benefits of a textile recycling process and, therefore, the related challenges towards more sustainable options. The considered textile recycling process incorporates mixed waste and is compared with landfills in terms of CO2eq because it represents the conventional treatment of waste and the substitution of products from primary sources. The results show that textile waste landfills emit 423.4 kg CO2eq per ton, while products from primary sources emit an average of 6496.65 kg CO2eq, compared to the textile recycling process that only it emits 1142.12 kg CO2eq per ton, obtaining an average of 5778 kg CO2eq avoided per ton of textile waste, achieving environmental benefits. However, it is necessary to highlight the dependence of this result on the choice of replaced products and the energy matrix. Thus, we assessed the energy matrix, evaluating the positive impact of implementing an energy matrix based on wind or solar energy.
Display omitted
•Increasing apparel consumption cause large textile wastes and environmental problems.•There is a need for environmentally friendly textile recycling alternatives.•The implementation of policies is necessary for an efficient textile waste management.•Changes in the energy matrix towards renewable energies are decisive.
•Lack of studies on market concentration both on the supply and demand sides.•Case: commercial and industrial non-hazardous solid waste in Chile.•Tonnes valorised stagnated and valorisation rate ...dropped between 2015 and 2019.•Top 10 percent generation companies concentrate 90 percent of tonnes generated.•Top generators also concentrate between 20 and 40 percent of valorisation.
Market concentration among buyers of recycled materials is a phenomenon discussed since the 1980 s by the anti-trust literature. Yet, there is still a lack of studies on simultaneous market concentration on both the supply and demand sides. This is particularly relevant when Extended Producer Responsibility (EPR) policies produce two-sided waste generation and valorisation markets. Thus, the purpose of this study is to explore the link between market concentration on the generation side and market share on the valorisation side. Specifically, this research addresses the case of valorisation of commercial and industrial non-hazardous waste in Chile. The analysis covers 261 companies that valorised industrial and commercial non-hazardous waste between 2015 and 2019. Being part of the top 10 % of generator companies in Chile is significantly correlated to higher valorisation market share, in a context in which mean market share per company decreased, total tons valorised stagnated, and the country-level valorisation rate diminished.
•A life-cycle assessment for MSW in regional cities from developing countries is shown.•The illustrative case of city of Valdivia (Chile) is studied.•An environmental performance analysis of six MSW ...management scenarios is carried out.•The waste-to-energy scenario shows the best performance in terms of GHG and energy.•From the results obtained, an alternative for heating the city is provided.
Municipal solid waste (MSW) management is an important challenge in developing and emerging countries, where two realities co-exist. On the one hand, their metropolitan cities exhibit an integrated MSW system with a specialized fleet for the collection and landfills for the final disposal, concentrating on environmental initiatives such as municipal recycling programs. On the other hand, their regional cities show an MSW system based on adapted transports for collection and open dumps for final disposal. Besides, they face other environmental problems due to local conditions. This research proposes a life cycle assessment (LCA) approach to close the gap between these two realities. In particular, we study the city of Valdivia (Chile), one of the main regional capitals of South America, which shares similarities with other southern regional cities in the Global South. This city disposes 95% of its MSW in open dumps and presents one of the highest environmental pollution rates in Latin America. We analyze the greenhouse gas (GHG) emissions and energy performance of six scenarios, seeking a solution for these problems. The results obtained show that a waste-to-energy scenario would generate savings of GHG emission and particulate matter, reaching 11.3% and 21.8%, respectively. Using our LCA approach, we can provide environmental evidence to highlight the importance of improving MSW management in regional cities, closing the gap with MSW management in metropolitan cities, and contributing to national targets such as United Nations Sustainable Development Goals and Nationally-Determined Contributions.
The $882 billion textile trade in 2021 poses environmental concerns, highlighting the importance of encouraging a circular economy to attain sustainable textiles. Therefore, policies must prioritize ...textile recycling, particularly in developing countries, and sharing information throughout the value chain. This research aims to explore the potential environmental benefits of two industrial recycling processes for textile residues versus the traditional waste management and production process through a life cycle assessment applying the ReCiPe method at midpoint and endpoint levels focusing on generating significant data availability and broader assessment than existing literature to support decision making related to recycling systems for textile residues. Results related to the textile residues recycling process to obtain stripes (R1) and replace sawdust, to fill pushing balls, show that it would produce environmental benefits regardless of location in several midpoint categories. Furthermore, regarding the endpoint results, the DALY savings are mainly due to avoiding landfill, while the savings in ecosystem impacts are generated by avoiding landfill and sawdust production. Regarding the recycling process to obtain recycled yarn and fill (R2) net savings in global warming potential are generated if landfill avoidance is considered. Nevertheless, endpoint results show that DALYs of all the avoided processes correspond to 1.5 times the impacts of all the R2 recycling processes, mainly due to avoiding virgin yarn production. Therefore, both recycling processes are recommended. However, some strategies are required to generate greater benefits, such as applying the R2 recycling process as the first option for stretchable textile waste, and after being used, going through the R1 recycling process. In addition, the strategic placement of the R1 recycling facility should be distant from areas of sawdust production. A sensitivity analysis was carried out due to the variability of virgin products to replace in the market.
Display omitted
•Textile residue recycling for pushing ball fill has environmental benefits.•Environmental benefit depends on plants' location for some recycling process.•There are several environmentally friendly textile recycling alternatives.
Purpose
Among the Sustainable Development Goals (SDG), the global warming and malnutrition relationship relies on food consumption patterns. It calls for a decisive change in food consumption ...patterns by offering nutritionally adequate, acceptable, affordable, and environmentally friendly menus in massive food services. Therefore, the research question can be defined as: Are there menus considering several servings, nutritionally adequate, acceptable, affordable, and environmentally friendly?
Methods
To address this problem, we focus on the dilemma between minimizing the equivalent carbon dioxide (
CO
2
eq
) emitted in the entire production process of a menu, the monthly acquisition cost, and the selection of the most nutritionally adequate menu possible. Specifically, we formulated three multi-objective quadratic mixed integer programming (QMIP) models: (i) minimization of
CO
2
eq
emissions and the selection of the most nutritionally adequate menu possible, (ii) minimization of the monthly acquisition cost of the system and the selection of the most nutritionally adequate menu possible, and (iii) the weighting of
CO
2
eq
emissions, the monthly acquisition cost, and the selection of the most nutritionally adequate menu possible. All are subject to the same nutritional constraints, operational requirements, and cultural acceptability. Chile is the case study to illustrate the proposal’s usefulness, which is one of the wealthiest countries in the Global South with the highest prevalence of overweight. In addition, Chile has addressed various international initiatives, where greenhouse gas reduction is one of the most important commitments. Consequently, alternatives to change food consumption patterns are required. We selected a prestigious Chilean public university in Santiago, which houses all the communities on a single campus. The university offers a daily lunch menu consisting of a starter, main dish, and dessert, considering a set of nutritional aspects: proteins, lipids, carbohydrates, saturated fatty acids, fiber, cholesterol, sodium, and calories.
Results
As a result of the 6-month optimization, minimizing acquisition costs proposes cheaper menus with higher
CO
2
eq
emissions than those proposed by the emission minimization. However, when both objective functions are weighted by 50%, results reach saved costs equivalent to 53,030 USD and emission reduction by around 94,900 kg
CO
2
eq
in the 6 months, compared to the data the menus delivered by the university.
Conclusions
It shows that, despite assessing conflicting objectives, it is possible to design nutritionally adequate, acceptable, affordable, and environmentally friendly menus for the case study presented. Future research considers solution approaches for multi-objective optimization as genetic algorithms and includes maximizing the number of servings to deliver.
PDF
