LIAAD - Indexed Articles in Journals
Permanent URI for this collection
Browse
Recent Submissions
1 - 5 of 241
-
ItemBranch-and-bound algorithms for minimizing total earliness and tardiness in a two-machine permutation flow shop with unforced idle allowed( 2019)The two-machine permutation flow shop scheduling problem with the objective of minimizing total earliness and tardiness is addressed. Unforced idle time can be used to complete jobs closer to their due dates. It is shown that unforced idle time only needs to be considered on the second machine. This result is then used to extend a lower bound and dominance conditions for the single-machine problem to the two-machine permutation flow shop problem. Two branch-and-bound algorithms are developed for the problem utilizing the lower bound and dominance conditions. The algorithms are tested using instances that represent a wide variety of conditions.
-
ItemMinimizing total earliness and tardiness in a nowait flow shop( 2020)This paper considers the problem of scheduling jobs in a no-wait flow shop with the objective of minimizing total earliness and tardiness. An exact branch-and-bound algorithm is developed for the problem. Several dispatching heuristics used previously for other environments and two new heuristics were tested under a variety of conditions. It was found that one of the new heuristics consistently performed well compared to the others. An insertion search improvement procedure with speed up methods based on the structure of the problem was proposed and was found to deliver much improved solutions in a reasonable amount of time.
-
ItemEfficient procedures for the weighted squared tardiness permutation flowshop scheduling problem( 2020)This paper addresses a permutation flowshop scheduling problem, with the objective of minimizing total weighted squared tardiness. The focus is on providing efficient procedures that can quickly solve medium or even large instances. Within this context, we first present multiple dispatching heuristics. These include general rules suited to various due date-related environments, heuristics developed for the problem with a linear objective function, and procedures that are suitably adapted to take the squared objective into account. Then, we describe several improvement procedures, which use one or more of three techniques. These procedures are used to improve the solution obtained by the best dispatching rule. Computational results show that the quadratic rules greatly outperform the linear counterparts, and that one of the quadratic rules is the overall best performing dispatching heuristic. The computational tests also show that all procedures significantly improve upon the initial solution. The non-dominated procedures, when considering both solution quality and runtime, are identified. The best dispatching rule, and two of the non-dominated improvement procedures, are quite efficient, and can be applied to even very large-sized problems. The remaining non-dominated improvement method can provide somewhat higher quality solutions, but it may need excessive time for extremely large instances.
-
Item
-
ItemEvolutionary dynamics for the generalized Baliga–Maskin public good model( 2019)The problem of the consumption or provision of common and public goods is a well known and well studied problem in economic sciences. The nature of the problem is the existence of non-excludable externalities which gives rise to incentives to free-riding behaviour. There are several economical frameworks trying to deal with the problem such as coalition theory or mechanism design and implementation theory to ensure a Pareto efficient consumption or provision of such good. Baliga and Maskin considered an environmental game where several communities face a problem of pollution reduction. They show that all communities except one of them have incentives to act as a free-rider, i.e. only one community is willing to face the costs that air cleaning implies, namely the one with greatest preference for the good. In this work we introduce an adaptive evolutionary dynamics for the generalization of the Baliga–Maskin model to quasi-linear utility functions. We show that the Baliga–Maskin equilibrium is the only asymptotically stable dynamical equilibrium, all others being unstable. This result reasserts the problem of free-riding and externalities for the case of a common good in a dynamically/evolutionary setting, and reiterates the relevance of mechanism design and coalition formation in the context of dynamical models. © 2019