
Journal of Scheduling [SJR: 1.417] [HI: 38] [3 followers] Follow Hybrid journal (It can contain Open Access articles) ISSN (Print) 10991425  ISSN (Online) 10946136 Published by SpringerVerlag [2335 journals] 
 A Step Counting Hill Climbing Algorithm applied to University Examination
Timetabling Abstract: Abstract
This paper presents a new singleparameter local search heuristic named step counting hill climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organised in different ways; therefore, the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the late acceptance hill climbing method, namely its convergence time is proportional to the value of its parameter and a nonlinear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study, we compare the new method with late acceptance hill climbing, simulated annealing and great deluge algorithm. The SCHC has shown the strongest performance on the most of our benchmark problems used.
PubDate: 20160801
 Abstract: Abstract
This paper presents a new singleparameter local search heuristic named step counting hill climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organised in different ways; therefore, the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the late acceptance hill climbing method, namely its convergence time is proportional to the value of its parameter and a nonlinear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study, we compare the new method with late acceptance hill climbing, simulated annealing and great deluge algorithm. The SCHC has shown the strongest performance on the most of our benchmark problems used.
 Temporal linear relaxation in IBM ILOG CP Optimizer
 Abstract: Abstract
IBM ILOG CP Optimizer is a constraint solver that implements a modelandrun paradigm. For scheduling problems, CP Optimizer provides a relatively simple but very expressive modeling language based on the notion of interval variables. This paper presents the temporal linear relaxation (TLR) used to guide the automatic search when solving scheduling problems that involve temporal and resource allocation costs. We give the rationale of the TLR, describe its integration in the automatic search of CP Optimizer, and present the relaxation of most of the constraints and expressions of the model. An experimental study on a set of classical scheduling benchmarks shows that using the TLR is essential for problems with irregular temporal costs and generally helps for problems with resource allocation costs.
PubDate: 20160801
 Abstract: Abstract
IBM ILOG CP Optimizer is a constraint solver that implements a modelandrun paradigm. For scheduling problems, CP Optimizer provides a relatively simple but very expressive modeling language based on the notion of interval variables. This paper presents the temporal linear relaxation (TLR) used to guide the automatic search when solving scheduling problems that involve temporal and resource allocation costs. We give the rationale of the TLR, describe its integration in the automatic search of CP Optimizer, and present the relaxation of most of the constraints and expressions of the model. An experimental study on a set of classical scheduling benchmarks shows that using the TLR is essential for problems with irregular temporal costs and generally helps for problems with resource allocation costs.
 Configuration and the advantages of the shifting bottleneck procedure for
optimizing the job shop total weighted tardiness scheduling problem Abstract: Abstract
This paper answers two fundamental questions concerning the usage of the shifting bottleneck (SB) procedure to optimize the criterion total weighted tardiness for the classical job shop scheduling problem. The first question is how to configure the SB procedure, as it is a divideandconquer method and consists of diverse subsolutions for each procedure phase. The second question is what the advantages of the SB procedure are, in comparison with other stateoftheart approaches. To answer the first question, we evaluate the performance (i.e. the scheduling quality) and the efficiency (i.e. the computational time) of various SB variants using computational experiments and present guidelines for configuring the SB procedure. To respond to the second question, extensive computational experiments were conducted on various benchmark instances (up to 100 jobs
\(\times \)
20 machines). Results show the superior performance/efficiency tradeoff of the SB variants with certain configuration to local search methods. This excellent tradeoff between performance and efficiency makes the SB procedure particularly promising for solving practical production scheduling problems.
PubDate: 20160801
 Abstract: Abstract
This paper answers two fundamental questions concerning the usage of the shifting bottleneck (SB) procedure to optimize the criterion total weighted tardiness for the classical job shop scheduling problem. The first question is how to configure the SB procedure, as it is a divideandconquer method and consists of diverse subsolutions for each procedure phase. The second question is what the advantages of the SB procedure are, in comparison with other stateoftheart approaches. To answer the first question, we evaluate the performance (i.e. the scheduling quality) and the efficiency (i.e. the computational time) of various SB variants using computational experiments and present guidelines for configuring the SB procedure. To respond to the second question, extensive computational experiments were conducted on various benchmark instances (up to 100 jobs
\(\times \)
20 machines). Results show the superior performance/efficiency tradeoff of the SB variants with certain configuration to local search methods. This excellent tradeoff between performance and efficiency makes the SB procedure particularly promising for solving practical production scheduling problems.
 A memetic algorithm to solve an unrelated parallel machine scheduling
problem with auxiliary resources in semiconductor manufacturing Abstract: Abstract
In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.
PubDate: 20160801
 Abstract: Abstract
In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.
 Late acceptance hillclimbing for high school timetabling
 Abstract: Abstract
The application of the Late Acceptance HillClimbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other stateofart methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHCbased algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.
PubDate: 20160801
 Abstract: Abstract
The application of the Late Acceptance HillClimbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other stateofart methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHCbased algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.
 Dynamic patient admission scheduling with operating room constraints,
flexible horizons, and patient delays Abstract: Abstract
We revisit and extend the patient admission scheduling problem, in order to make it suitable for practical applications. The main novelty is that we consider constraints on the utilisation of operating rooms for patients requiring a surgery. In addition, we propose a more elaborate model that includes a flexible planning horizon, a complex notion of patient delay, and new components of the objective function. We design a solution approach based on local search, which explores the search space using a composite neighbourhood. In addition, we develop an instance generator that uses realworld data and statistical distributions so as to synthesise realistic and challenging case studies, which are made available on the web along with our solutions and the validator. Finally, we perform an extensive experimental evaluation of our solution method including statistically principled parameter tuning and an analysis of some features of the model and their corresponding impact on the objective function.
PubDate: 20160801
 Abstract: Abstract
We revisit and extend the patient admission scheduling problem, in order to make it suitable for practical applications. The main novelty is that we consider constraints on the utilisation of operating rooms for patients requiring a surgery. In addition, we propose a more elaborate model that includes a flexible planning horizon, a complex notion of patient delay, and new components of the objective function. We design a solution approach based on local search, which explores the search space using a composite neighbourhood. In addition, we develop an instance generator that uses realworld data and statistical distributions so as to synthesise realistic and challenging case studies, which are made available on the web along with our solutions and the validator. Finally, we perform an extensive experimental evaluation of our solution method including statistically principled parameter tuning and an analysis of some features of the model and their corresponding impact on the objective function.
 Lawler’s minmax cost algorithm: optimality conditions and
uncertainty Abstract: Abstract
The wellknown
\(O(n^2)\)
minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an
\(O(n^2)\)
algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.
PubDate: 20160801
 Abstract: Abstract
The wellknown
\(O(n^2)\)
minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an
\(O(n^2)\)
algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.
 A purely proactive scheduling procedure for the resourceconstrained
project scheduling problem with stochastic activity durations Abstract: Abstract
The purpose of this research is to develop a new procedure for generating a proactive baseline schedule for the resourceconstrained project scheduling problem. The main advantage of this new procedure is that it is completely independent of the reactive policy applied. This contrasts with the traditional methods that assume a predefined reactive policy. First, we define a new robustness measure, then we introduce a branchandcut method for solving a sample average approximation of our original problem. In a computational experiment, we show that our procedure outperforms two other published methods, assuming different robustness measures.
PubDate: 20160801
 Abstract: Abstract
The purpose of this research is to develop a new procedure for generating a proactive baseline schedule for the resourceconstrained project scheduling problem. The main advantage of this new procedure is that it is completely independent of the reactive policy applied. This contrasts with the traditional methods that assume a predefined reactive policy. First, we define a new robustness measure, then we introduce a branchandcut method for solving a sample average approximation of our original problem. In a computational experiment, we show that our procedure outperforms two other published methods, assuming different robustness measures.
 Scheduling evacuation operations
 Abstract: Abstract
In this paper, we consider a largescale evacuation problem after a major disaster. The evacuation is assumed to occur by means of a fleet of buses, thus leading to scheduling the evacuation operations by buses [(bus evacuation problem (BEP)]. We propose timeindexed formulations as well as heuristic algorithms such as greedy algorithms and a matheuristic. This matheuristic uses the former formulation to improve the best solution obtained by the greedy heuristics. In computational experiments, we analyze and evaluate the efficiency of the proposed solution algorithms.
PubDate: 20160801
 Abstract: Abstract
In this paper, we consider a largescale evacuation problem after a major disaster. The evacuation is assumed to occur by means of a fleet of buses, thus leading to scheduling the evacuation operations by buses [(bus evacuation problem (BEP)]. We propose timeindexed formulations as well as heuristic algorithms such as greedy algorithms and a matheuristic. This matheuristic uses the former formulation to improve the best solution obtained by the greedy heuristics. In computational experiments, we analyze and evaluate the efficiency of the proposed solution algorithms.
 Continuoustime production, distribution and financial planning with
periodic liquidity balancing Abstract: Abstract
Due to the inevitable focus on core competencies, even small and mediumsized companies are increasingly forced to form supply chain (SC) networks. However, their specific situation is often characterized by a lack of equity and limited access to capital markets, so that bank loans must then be used to initiate production and distribution. Within a shortterm multiday planning horizon, both operations and finance must be scheduled precisely in order to obtain practical instructions for each network partner and the network managers. For this purpose, continuoustime modeling is required. Additionally, a coordination of monetary consequences resulting from both sitespecific operational events and networkwide financial transactions is necessary to prevent insolvency. As bank overdrafts can be used to overcome financial imbalances during short periods (e.g., days or even hours), appropriate time intervals for liquidity management should be determined. The implementation of these intervals requires discretetime modeling. In this context, the main challenge is to combine both of the aforementioned modeling techniques within a common decision model. To address this problem, a novel mixedinteger nonlinear program (MINLP) is developed, which enables exact planning and scheduling of SC operations as well as related financial transactions on the one hand, and periodic liquidity balancing on the other hand. A numerical analysis was based on a test scenario with randomly generated data. As we found out that even small problem instances of the MINLP, e.g., a threestage supply chain with three sites in each stage, were not computable with highperformance hardware and a commercial nonlinear standard solver, we additionally propose an equivalent linearized version of the decision model. The latter could be optimized within acceptable computation time using the CPLEX solver.
PubDate: 20160709
 Abstract: Abstract
Due to the inevitable focus on core competencies, even small and mediumsized companies are increasingly forced to form supply chain (SC) networks. However, their specific situation is often characterized by a lack of equity and limited access to capital markets, so that bank loans must then be used to initiate production and distribution. Within a shortterm multiday planning horizon, both operations and finance must be scheduled precisely in order to obtain practical instructions for each network partner and the network managers. For this purpose, continuoustime modeling is required. Additionally, a coordination of monetary consequences resulting from both sitespecific operational events and networkwide financial transactions is necessary to prevent insolvency. As bank overdrafts can be used to overcome financial imbalances during short periods (e.g., days or even hours), appropriate time intervals for liquidity management should be determined. The implementation of these intervals requires discretetime modeling. In this context, the main challenge is to combine both of the aforementioned modeling techniques within a common decision model. To address this problem, a novel mixedinteger nonlinear program (MINLP) is developed, which enables exact planning and scheduling of SC operations as well as related financial transactions on the one hand, and periodic liquidity balancing on the other hand. A numerical analysis was based on a test scenario with randomly generated data. As we found out that even small problem instances of the MINLP, e.g., a threestage supply chain with three sites in each stage, were not computable with highperformance hardware and a commercial nonlinear standard solver, we additionally propose an equivalent linearized version of the decision model. The latter could be optimized within acceptable computation time using the CPLEX solver.
 An exact extended formulation for the unrelated parallel machine total
weighted completion time problem Abstract: Abstract
The plethora of research on
\(\mathcal {NP}\)
hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a nonpreemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decompositionbased algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
PubDate: 20160621
 Abstract: Abstract
The plethora of research on
\(\mathcal {NP}\)
hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a nonpreemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decompositionbased algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
 Minimizing worstcase and averagecase makespan over scenarios
 Abstract: Abstract
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.
PubDate: 20160617
 Abstract: Abstract
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.
 Reordering buffer management with advice
 Abstract: Abstract
In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any
\(\varepsilon > 0\)
there is a
\((1+\varepsilon )\)
competitive algorithm for the problem which uses only a constant (depending on
\(\varepsilon \)
) number of advice bits per input item. This also immediately implies a
\((1+\varepsilon )\)
approximation algorithm which has
\(2^{O(n\log 1/\varepsilon )}\)
running time (this should be compared to the trivial optimal algorithm which has a running time of
\(k^{O(n)}\)
). We complement the above result by presenting a lower bound of
\(\varOmega (\log k)\)
bits of advice per request for any 1competitive algorithm.
PubDate: 20160617
 Abstract: Abstract
In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any
\(\varepsilon > 0\)
there is a
\((1+\varepsilon )\)
competitive algorithm for the problem which uses only a constant (depending on
\(\varepsilon \)
) number of advice bits per input item. This also immediately implies a
\((1+\varepsilon )\)
approximation algorithm which has
\(2^{O(n\log 1/\varepsilon )}\)
running time (this should be compared to the trivial optimal algorithm which has a running time of
\(k^{O(n)}\)
). We complement the above result by presenting a lower bound of
\(\varOmega (\log k)\)
bits of advice per request for any 1competitive algorithm.
 Optimal scheduling of contract algorithms with soft deadlines
 Abstract: Abstract
A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a wellstudied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time
\(w(t)\le c \cdot t\)
, for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.
PubDate: 20160616
 Abstract: Abstract
A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a wellstudied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time
\(w(t)\le c \cdot t\)
, for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.
 Preface
 PubDate: 20160601
 PubDate: 20160601
 Uplink scheduling for joint wireless orthogonal frequency and time
division multiple access networks Abstract: Abstract
In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary secondorder conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for nonrealtime applications where subchannel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.
PubDate: 20160601
 Abstract: Abstract
In this paper, we present a deterministic resource allocation model for a hybrid uplink wireless orthogonal frequency and time division multiple access network. Since the input data of the model may be affected by uncertainty, we further consider a stochastic formulation of the problem which we transform into an equivalent deterministic binary secondorder conic program (SOCP). Subsequently, we use this binary SOCP to derive an equivalent integer linear programming formulation. The proposed models are aimed at maximizing the total bandwidth channel capacity subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. As such, the models are best suited for nonrealtime applications where subchannel multiuser diversity can be further exploited simultaneously in frequency and time domains. Finally, in view of the large execution times required by CPLEX to solve the proposed models, we propose a variable neighborhood search metaheuristic procedure. Our numerical results show tight bounds and near optimal solutions for most of the instances when compared to the optimal solution of the problem. Moreover, we obtain better feasible solutions than CPLEX in the stochastic case. Finally, these bounds are obtained at a very low computational cost.
 Line search method for solving a nonpreemptive strictly periodic
scheduling problem Abstract: Abstract
We study a nonpreemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of
\(N\)
periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on
\(P\)
processors distributed on the plane. In this article, we consider an existing heuristic which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and, therefore, to produce the best response, given the other schedules. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions.
PubDate: 20160601
 Abstract: Abstract
We study a nonpreemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of
\(N\)
periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on
\(P\)
processors distributed on the plane. In this article, we consider an existing heuristic which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and, therefore, to produce the best response, given the other schedules. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions.
 Novel dual discounting functions for the Internet shopping optimization
problem: new algorithms Abstract: Abstract
One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment.
PubDate: 20160601
 Abstract: Abstract
One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment.
 Exact algorithms for singlemachine scheduling with time windows and
precedence constraints Abstract: Abstract
We study a singlemachine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unittime delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branchandbound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving mediumsized instances, and that it compares favorably with existing methods for special cases of the problem.
PubDate: 20160601
 Abstract: Abstract
We study a singlemachine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unittime delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branchandbound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving mediumsized instances, and that it compares favorably with existing methods for special cases of the problem.
 A decision support approach to automatic timetabling in higher education
institutions Abstract: Abstract
At a time when the need to reduce costs has become part of the daytoday reality of all educational institutions, it is unthinkable to continue to manually perform those tasks (i.e., the creation of timetables) that can be automated and optimized. The automatic creation of timetables for educational institutions is one of the most studied problems by the scientific community. However, almost all studies have been based on very simplified models of reality that have no practical application. A realistic model of the problem, robust algorithms that are able to find valid solutions in highly restricted environments, and optimization methods that are able to quickly provide quality results are key factors to consider when attempting to solve this (real) problem faced by educational institutions. This paper presents a summary of the work performed by Bullet Solutions over the last few years, from the first stage of understanding and modelling the problem to the final analysis of the results obtained using the developed software under real conditions.
PubDate: 20160601
 Abstract: Abstract
At a time when the need to reduce costs has become part of the daytoday reality of all educational institutions, it is unthinkable to continue to manually perform those tasks (i.e., the creation of timetables) that can be automated and optimized. The automatic creation of timetables for educational institutions is one of the most studied problems by the scientific community. However, almost all studies have been based on very simplified models of reality that have no practical application. A realistic model of the problem, robust algorithms that are able to find valid solutions in highly restricted environments, and optimization methods that are able to quickly provide quality results are key factors to consider when attempting to solve this (real) problem faced by educational institutions. This paper presents a summary of the work performed by Bullet Solutions over the last few years, from the first stage of understanding and modelling the problem to the final analysis of the results obtained using the developed software under real conditions.