
Journal of Scheduling [SJR: 1.417] [HI: 38] [2 followers] Follow Hybrid journal (It can contain Open Access articles) ISSN (Print) 10991425  ISSN (Online) 10946136 Published by SpringerVerlag [2281 journals] 
 Realtime management of berth allocation with stochastic arrival and
handling times Abstract: Abstract
In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimizationbased recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the realworld issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.
PubDate: 20160423
 Abstract: Abstract
In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimizationbased recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the realworld issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.
 Unary NPhardness of minimizing the number of tardy jobs with deadlines
 Abstract: Abstract
For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NPhard. But the exact complexity (unary NPhard or pseudopolynomialtime solvability) is a long standing open problem. We show in this paper that the problem is unary NPhard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NPhard. As a consequence, some multiagent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NPhard.
PubDate: 20160422
 Abstract: Abstract
For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NPhard. But the exact complexity (unary NPhard or pseudopolynomialtime solvability) is a long standing open problem. We show in this paper that the problem is unary NPhard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NPhard. As a consequence, some multiagent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NPhard.
 An exact algorithm for parallel machine scheduling with conflicts
 Abstract: Abstract
We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.
PubDate: 20160422
 Abstract: Abstract
We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.
 Improved approaches to the exact solution of the machine covering problem
 Abstract: Abstract
For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branchandbound algorithm. Its most distinctive components are a different symmetrybreaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.
PubDate: 20160422
 Abstract: Abstract
For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branchandbound algorithm. Its most distinctive components are a different symmetrybreaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.
 Scheduling with timedependent discrepancy times
 Abstract: Abstract
In timedependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This singlemachine scheduling problem with timedependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branchandbound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomialtime algorithm.
PubDate: 20160415
 Abstract: Abstract
In timedependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This singlemachine scheduling problem with timedependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branchandbound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomialtime algorithm.
 A parameterized complexity view on nonpreemptively scheduling
 Abstract: Abstract
We study the problem of nonpreemptively scheduling n jobs, each job j with a release time
\(t_j\)
, a deadline
\(d_j\)
, and a processing time
\(p_j\)
, on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints
\( d_jt_j \le \lambda {}p_j\)
and
\( d_jt_j \le p_j +\sigma \)
and showed the problem to be NPhard for any
\(\lambda >1\)
and for any
\(\sigma \ge 2\)
. We complement their results by parameterized complexity studies: we show that, for any
\(\lambda >1\)
, the problem remains weakly NPhard even for
\(m=2\)
and strongly W[1]hard parameterized by m. We present a pseudopolynomialtime algorithm for constant m and
\(\lambda \)
and a fixedparameter tractability result for the parameter m combined with
\(\sigma \)
.
PubDate: 20160408
 Abstract: Abstract
We study the problem of nonpreemptively scheduling n jobs, each job j with a release time
\(t_j\)
, a deadline
\(d_j\)
, and a processing time
\(p_j\)
, on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints
\( d_jt_j \le \lambda {}p_j\)
and
\( d_jt_j \le p_j +\sigma \)
and showed the problem to be NPhard for any
\(\lambda >1\)
and for any
\(\sigma \ge 2\)
. We complement their results by parameterized complexity studies: we show that, for any
\(\lambda >1\)
, the problem remains weakly NPhard even for
\(m=2\)
and strongly W[1]hard parameterized by m. We present a pseudopolynomialtime algorithm for constant m and
\(\lambda \)
and a fixedparameter tractability result for the parameter m combined with
\(\sigma \)
.
 Preemptive scheduling on uniformly related machines: minimizing the sum of
the largest pair of job completion times Abstract: Abstract
We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.
PubDate: 20160406
 Abstract: Abstract
We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.
 Necessary and sufficient optimality conditions for scheduling unit time
jobs on identical parallel machines Abstract: Abstract
In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
PubDate: 20160402
 Abstract: Abstract
In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
 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: 20160402
 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.
 Measuring the impact of adversarial errors on packet scheduling strategies
 Abstract: Abstract
In this paper, we explore the problem of achieving efficient packet transmission over unreliable links with worstcase occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic throughput metric which corresponds to the longterm competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous with deferred error feedback, which requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worstcase adversarial and stochastic packet arrival models, and formally analyze their performance. The asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.
PubDate: 20160401
 Abstract: Abstract
In this paper, we explore the problem of achieving efficient packet transmission over unreliable links with worstcase occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic throughput metric which corresponds to the longterm competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous with deferred error feedback, which requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worstcase adversarial and stochastic packet arrival models, and formally analyze their performance. The asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.
 Optimal K unit cycle scheduling of twocluster tools with residency
constraints and general robot moving times Abstract: Abstract
The semiconductor manufacturing industry is significantly expensive both in equipment and materials. Cluster tools, a type of automated manufacturing system integrating processing modules and transport modules, are commonly used in this industry. Nowadays, multicluster tools, which are composed of several cluster tools connected by joint buffer modules, are often used for wafer production. This paper deals with Kunit cycle scheduling problems in singlearmed twocluster tools for processing identical wafers in deterministic settings. In a Kunit cycle, K wafers are exactly inserted into the twocluster tool, and K completed wafers leave the twocluster tool, usually not the same K wafers. Residency constraints and general moving times by the robot are both considered. The objective is to obtain optimal Kunit cycle schedules, which minimize cycle times. To analyze this scheduling problem in detail, a mixed integer linear programming (MILP) model is formulated and solved. Numerical examples are used to explain how the solution can be obtained from the MILP model in a Kunit cycle.
PubDate: 20160401
 Abstract: Abstract
The semiconductor manufacturing industry is significantly expensive both in equipment and materials. Cluster tools, a type of automated manufacturing system integrating processing modules and transport modules, are commonly used in this industry. Nowadays, multicluster tools, which are composed of several cluster tools connected by joint buffer modules, are often used for wafer production. This paper deals with Kunit cycle scheduling problems in singlearmed twocluster tools for processing identical wafers in deterministic settings. In a Kunit cycle, K wafers are exactly inserted into the twocluster tool, and K completed wafers leave the twocluster tool, usually not the same K wafers. Residency constraints and general moving times by the robot are both considered. The objective is to obtain optimal Kunit cycle schedules, which minimize cycle times. To analyze this scheduling problem in detail, a mixed integer linear programming (MILP) model is formulated and solved. Numerical examples are used to explain how the solution can be obtained from the MILP model in a Kunit cycle.
 Relocation scheduling subject to fixed processing sequences
 Abstract: Abstract
This study addresses a relocation scheduling problem that corresponds to resourceconstrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in
\(O(n_1n_2(n_1+n_2))\)
time, where
\(n_1\)
and
\(n_2\)
are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in
\(O(n_1n_2)\)
time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NPhard in the ordinary sense, and the case with a common job processing length is solvable in
\(O(n_1n_2\min \{n_1,n_2\})\)
time. The studied problem for the minimization of number of tardy jobs is solvable in
\(O(n^2_1n^2_2(n_1+n_2)^2)\)
time. The solvability of the commonprocessingtime problems can be generalized to the mmachine cases, where
\(m\ge 3\)
.
PubDate: 20160401
 Abstract: Abstract
This study addresses a relocation scheduling problem that corresponds to resourceconstrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in
\(O(n_1n_2(n_1+n_2))\)
time, where
\(n_1\)
and
\(n_2\)
are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in
\(O(n_1n_2)\)
time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NPhard in the ordinary sense, and the case with a common job processing length is solvable in
\(O(n_1n_2\min \{n_1,n_2\})\)
time. The studied problem for the minimization of number of tardy jobs is solvable in
\(O(n^2_1n^2_2(n_1+n_2)^2)\)
time. The solvability of the commonprocessingtime problems can be generalized to the mmachine cases, where
\(m\ge 3\)
.
 An exact algorithm for an integrated project staffing problem with a
homogeneous workforce Abstract: Abstract
When scheduling projects under resource constraints, assumptions are typically made with respect to the resource availability. In resource scheduling problems important assumptions are made with respect to the resource requirements. As projects are typically labour intensive, the underlying (personnel) resource scheduling problems tend to be complex due to different rules and regulations. In this paper, we aim to integrate these two interrelated scheduling problems to minimise the overall cost. For that purpose, we propose an exact algorithm for the project staffing with resource scheduling constraints. Detailed computational experiments are presented to evaluate different branching rules and pruning strategies and to compare the proposed procedure with other optimisation techniques.
PubDate: 20160401
 Abstract: Abstract
When scheduling projects under resource constraints, assumptions are typically made with respect to the resource availability. In resource scheduling problems important assumptions are made with respect to the resource requirements. As projects are typically labour intensive, the underlying (personnel) resource scheduling problems tend to be complex due to different rules and regulations. In this paper, we aim to integrate these two interrelated scheduling problems to minimise the overall cost. For that purpose, we propose an exact algorithm for the project staffing with resource scheduling constraints. Detailed computational experiments are presented to evaluate different branching rules and pruning strategies and to compare the proposed procedure with other optimisation techniques.
 Ant colony systems for the singlemachine total weighted earliness
tardiness scheduling problem Abstract: Abstract
Singlemachine weighted earliness tardiness scheduling is a prevalent problem in justintime production environments. Yet, the case with distinct due dates is strongly NPhard. Herein, it is approximately solved using ASV, an ant colonybased system with a reduced number of ants and of colonies and with daemon actions that explore the search space around the ants using a variable neighborhood search (VNS). The numerical investigation provides computational proof of the utility of the daemon actions. In addition, it infers that these latter can be applied either to the initial or to subsequent colonies. Furthermore, it highlights the importance of using ant colony optimization as the multiple restart engine of VNS. Finally, it shows that ASV obtains the optimum for most smallsized instances. It has a 0.2 % average deviation from the optimum over all benchmark instances.
PubDate: 20160401
 Abstract: Abstract
Singlemachine weighted earliness tardiness scheduling is a prevalent problem in justintime production environments. Yet, the case with distinct due dates is strongly NPhard. Herein, it is approximately solved using ASV, an ant colonybased system with a reduced number of ants and of colonies and with daemon actions that explore the search space around the ants using a variable neighborhood search (VNS). The numerical investigation provides computational proof of the utility of the daemon actions. In addition, it infers that these latter can be applied either to the initial or to subsequent colonies. Furthermore, it highlights the importance of using ant colony optimization as the multiple restart engine of VNS. Finally, it shows that ASV obtains the optimum for most smallsized instances. It has a 0.2 % average deviation from the optimum over all benchmark instances.
 A note on longest processing time algorithms for the two uniform parallel
machine makespan minimization problem Abstract: Abstract
This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worstcase performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.
PubDate: 20160401
 Abstract: Abstract
This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worstcase performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.
 Single machine scheduling problems with uncertain parameters and the OWA
criterion Abstract: Abstract
In this paper a class of single machine scheduling problems is discussed. It is assumed that job parameters, such as processing times, due dates, or weights are uncertain and their values are specified in the form of a discrete scenario set. The ordered weighted averaging (OWA) aggregation operator is used to choose an optimal schedule. The OWA operator generalizes traditional criteria used in decision making under uncertainty, such as the maximum, average, median, or Hurwicz criterion. It also allows us to extend the robust approach to scheduling by taking into account various attitudes of decision makers towards a risk. In this paper, a general framework for solving single machine scheduling problems with the OWA criterion is proposed and some positive and negative computational results for two basic single machine scheduling problems are provided.
PubDate: 20160401
 Abstract: Abstract
In this paper a class of single machine scheduling problems is discussed. It is assumed that job parameters, such as processing times, due dates, or weights are uncertain and their values are specified in the form of a discrete scenario set. The ordered weighted averaging (OWA) aggregation operator is used to choose an optimal schedule. The OWA operator generalizes traditional criteria used in decision making under uncertainty, such as the maximum, average, median, or Hurwicz criterion. It also allows us to extend the robust approach to scheduling by taking into account various attitudes of decision makers towards a risk. In this paper, a general framework for solving single machine scheduling problems with the OWA criterion is proposed and some positive and negative computational results for two basic single machine scheduling problems are provided.
 Nonpreemptive buffer management for latency sensitive packets
 Abstract: Abstract
The delivery of latency sensitive packets is a crucial issue in realtime applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a nonpreemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a realvalued model, where any value over 1 is allowed, and an integralvalued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the realvalued model, we give a randomized 4competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of
\(\phi ^3  {\varepsilon }\approx 4.236\)
, almost matching the previously known 4.24competitive algorithm. For the integralvalued model, we describe a deterministic 4competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).
PubDate: 20160317
 Abstract: Abstract
The delivery of latency sensitive packets is a crucial issue in realtime applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a nonpreemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a realvalued model, where any value over 1 is allowed, and an integralvalued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the realvalued model, we give a randomized 4competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of
\(\phi ^3  {\varepsilon }\approx 4.236\)
, almost matching the previously known 4.24competitive algorithm. For the integralvalued model, we describe a deterministic 4competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).
 Highmultiplicity scheduling on one machine with forbidden start and
completion times Abstract: Abstract
We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the highmultiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixedparameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.
PubDate: 20160317
 Abstract: Abstract
We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the highmultiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixedparameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.
 An integrated model for the transshipment yard scheduling problem
 Abstract: Abstract
A hubandspoke railway system is an efficient way of handling freight transport by land. A modern rail–rail train yard consists of huge gantry cranes that move the containers between the trains. In this context, we consider a rail–rail transshipment yard scheduling problem (TYSP) where the containers arrive to the hub and need to be placed on a train that will deliver them to their destination. In the literature, the problem is decomposed hierarchically into five subproblems, which are solved separately. First, the trains have to be grouped into bundles in which they visit the yard. Next, the trains have to be assigned to tracks within these bundles, namely parking positions. Then the final positions for the containers on trains have to be determined. Next, the container moves that need to be performed are assigned to the cranes. Finally, these moves have to be sequenced for each crane for processing. In this paper, an integrated MILP model is proposed, which aims to solve the TYSP as a single optimization problem. The proposed formulation also enables us to define more robust and complex objective functions that include key characteristics from each of the abovementioned subproblems. The strength of our proposed formulation is demonstrated via computational experiments using the data from the literature. Indeed, the results show that the TYSP can be solved without the use of decomposition techniques and more insight can be obtained from the same input data used to solve particular single decomposed subproblems.
PubDate: 20160316
 Abstract: Abstract
A hubandspoke railway system is an efficient way of handling freight transport by land. A modern rail–rail train yard consists of huge gantry cranes that move the containers between the trains. In this context, we consider a rail–rail transshipment yard scheduling problem (TYSP) where the containers arrive to the hub and need to be placed on a train that will deliver them to their destination. In the literature, the problem is decomposed hierarchically into five subproblems, which are solved separately. First, the trains have to be grouped into bundles in which they visit the yard. Next, the trains have to be assigned to tracks within these bundles, namely parking positions. Then the final positions for the containers on trains have to be determined. Next, the container moves that need to be performed are assigned to the cranes. Finally, these moves have to be sequenced for each crane for processing. In this paper, an integrated MILP model is proposed, which aims to solve the TYSP as a single optimization problem. The proposed formulation also enables us to define more robust and complex objective functions that include key characteristics from each of the abovementioned subproblems. The strength of our proposed formulation is demonstrated via computational experiments using the data from the literature. Indeed, the results show that the TYSP can be solved without the use of decomposition techniques and more insight can be obtained from the same input data used to solve particular single decomposed subproblems.
 An analysis of the nonpreemptive mixedcriticality matchup scheduling
problem Abstract: Abstract
Many applications have a mixedcriticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixedcriticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated offline, but its online execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the nonpreemptive mixedcriticality matchup scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3partition problem, we prove the problem to be
\(\mathcal {NP}\)
hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.
PubDate: 20160307
 Abstract: Abstract
Many applications have a mixedcriticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixedcriticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated offline, but its online execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the nonpreemptive mixedcriticality matchup scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3partition problem, we prove the problem to be
\(\mathcal {NP}\)
hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.