
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 [2335 journals] 
 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.
 The MultiMode ResourceConstrained MultiProject Scheduling Problem
 Abstract: Abstract
Scheduling projects is a difficult and time consuming process, and has farreaching implications for any organization’s operations. By generalizing various aspects of project scheduling, decision makers are enabled to capture reality and act accordingly. In the context of the MISTA 2013 conference, the first MISTA challenge, organized by the authors, introduced such a general problem model: the MultiMode ResourceConstrained MultiProject Scheduling Problem (MRCMPSP). The present paper reports on the competition and provides a discussion on its results. Furthermore, it provides an analysis of the submitted algorithms, and a study of their common elements. By making all benchmark datasets and results publicly available, further research on the MRCMPSP is stimulated.
PubDate: 20160601
 Abstract: Abstract
Scheduling projects is a difficult and time consuming process, and has farreaching implications for any organization’s operations. By generalizing various aspects of project scheduling, decision makers are enabled to capture reality and act accordingly. In the context of the MISTA 2013 conference, the first MISTA challenge, organized by the authors, introduced such a general problem model: the MultiMode ResourceConstrained MultiProject Scheduling Problem (MRCMPSP). The present paper reports on the competition and provides a discussion on its results. Furthermore, it provides an analysis of the submitted algorithms, and a study of their common elements. By making all benchmark datasets and results publicly available, further research on the MRCMPSP is stimulated.
 Timehierarchical scheduling
 Abstract: Abstract
In this paper, the general time hierarchical planning and scheduling approach is introduced, which integrates both detailed scheduling and due date assignment for an online problem. In this approach, time is divided into intervals of increasing size, and the different sizes form a hierarchy. We show that for a simplified model, a multiple level bin packing approach is an approximation algorithm, and we further prove that under weak assumptions, the approximation quality is bounded independently of the depth of the hierarchy.
PubDate: 20160601
 Abstract: Abstract
In this paper, the general time hierarchical planning and scheduling approach is introduced, which integrates both detailed scheduling and due date assignment for an online problem. In this approach, time is divided into intervals of increasing size, and the different sizes form a hierarchy. We show that for a simplified model, a multiple level bin packing approach is an approximation algorithm, and we further prove that under weak assumptions, the approximation quality is bounded independently of the depth of the hierarchy.
 Reallife examination timetabling
 Abstract: Abstract
An examination timetabling problem at a large American university is presented. Although there are some important differences, the solution approach is based on the ITC 2007 winning solver which is integrated in the open source university timetabling system UniTime. In this work, nine real world benchmark data sets are made publicly available and the results on four of them are presented in this paper. A new approach to further decreasing the number of student conflicts by allowing some exams to be split into multiple examination periods is also studied.
PubDate: 20160601
 Abstract: Abstract
An examination timetabling problem at a large American university is presented. Although there are some important differences, the solution approach is based on the ITC 2007 winning solver which is integrated in the open source university timetabling system UniTime. In this work, nine real world benchmark data sets are made publicly available and the results on four of them are presented in this paper. A new approach to further decreasing the number of student conflicts by allowing some exams to be split into multiple examination periods is also studied.
 An integer programming approach to the multimode resourceconstrained
multiproject scheduling problem Abstract: Abstract
The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.
PubDate: 20160601
 Abstract: Abstract
The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.
 A complexity analysis and an algorithmic approach to student sectioning in
existing timetables Abstract: Abstract
We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign
\(m\)
students to
\(k\)
sectioned courses with respect to a given timetable with
\(l\)
timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in
\(O( k^2l^2 \log (\mathrm{sum}_{A}))\)
, where
\(\mathrm{sum}_{A}\)
is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NPcomplete problem:
Courseselection constraint: Student’s courseselections must be respected.
Timeslot constraint: Students have individual timeslot restrictions.
Multipleevent constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all sectionevents for each student.
Hence our investigation gives insight into the location of the borderline between efficiently solvable and computationally hard problem variations.
PubDate: 20160601
 Abstract: Abstract
We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign
\(m\)
students to
\(k\)
sectioned courses with respect to a given timetable with
\(l\)
timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in
\(O( k^2l^2 \log (\mathrm{sum}_{A}))\)
, where
\(\mathrm{sum}_{A}\)
is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NPcomplete problem:
Courseselection constraint: Student’s courseselections must be respected.
Timeslot constraint: Students have individual timeslot restrictions.
Multipleevent constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all sectionevents for each student.
Hence our investigation gives insight into the location of the borderline between efficiently solvable and computationally hard problem variations.
 Finding optimal tour schedules on transportation paths under extended time
window constraints Abstract: Abstract
This paper addresses timecritical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the wellknown LineTraveling Repairman problem (LineTRPTW) is extended into the LineTRPeTW. The LineTRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the LineTRPTW/LineTRPeTW is known to be strongly
\({\mathcal {NP}}\)
hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary
\({\mathcal {NP}}\)
hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudopolynomial time.
PubDate: 20160512
 Abstract: Abstract
This paper addresses timecritical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the wellknown LineTraveling Repairman problem (LineTRPTW) is extended into the LineTRPeTW. The LineTRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the LineTRPTW/LineTRPeTW is known to be strongly
\({\mathcal {NP}}\)
hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary
\({\mathcal {NP}}\)
hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudopolynomial time.
 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.