JournalTOCs

Journal of Scheduling

[4 followers] Follow
Full-text available via subscription

Subscription journal
ISSN (Print) 1099-1425 - ISSN (Online) 1094-6136
Published by Springer-Verlag

[2218 journals]

Aircraft landing problems with aircraft classes
- Abstract: This article focuses on the aircraft landing problem that is to assign landing times to aircraft approaching the airport under consideration. Each aircraft’s landing time must be in a time interval encompassing a target landing time. If the actual landing time deviates from the target landing time additional costs occur which depend on the amount of earliness and lateness, respectively. The objective is to minimize overall cost. We consider the set of aircraft being partitioned into aircraft classes such that two aircraft of the same class are equal with respect to wake turbulence. We develop algorithms to solve the corresponding problem. Analyzing the worst case run-time behavior, we show that our algorithms run in polynomial time for fairly general cases of the problem. Moreover, we present integer programming models. We show by means of a computational study how optimality properties can be used to increase efficiency of standard solvers.
  PubDate: 2013-06-15
A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem
- Abstract: The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.
  PubDate: 2013-06-12
Stochastic scheduling problems with general position-based learning effects and stochastic breakdowns
- Abstract: The focus of this study is to analyze position-based learning effects in single-machine stochastic scheduling problems. The optimal permutation policies for the stochastic scheduling problems with and without machine breakdowns are examined, where the performance measures are the expectation and variance of the makespan, the expected total completion time, the expected total weighted completion time, the expected weighted sum of the discounted completion times, the maximum lateness and the maximum tardiness.
  PubDate: 2013-06-01
Scheduling of inventory releasing jobs to minimize a regular objective function of delivery times
- Abstract: In this note we provide new complexity and algorithmic results for scheduling inventory releasing jobs, a new class of single machine scheduling problems proposed recently by Boysen et al. We focus on tardiness related criteria, while known results are concerned with inventory levels between fixed delivery points. Our interest is motivated by the fact that deciding whether a feasible schedule exists is NP-hard in the strong sense, provided that all delivery deadlines are fixed, and there are no restrictions on the amount of products released by the jobs, nor on the job processing times. We will establish NP-hardness results, or provide polynomial or pseudo-polynomial time algorithms for various special cases, and describe a fully polynomial approximation scheme for one of the variants with the maximum tardiness criterion.
  PubDate: 2013-06-01
Single machine scheduling with delivery dates and cumulative payoffs
- Abstract: We address a single machine scheduling problem with a new optimization criterion and unequal release dates. This new criterion results from a practical situation in the domain of book digitization. Given a set of job-independent delivery dates, the goal is to maximize the cumulative number of jobs processed before each delivery date. We establish the complexity of the general problem. In addition, we discuss some polynomial cases and provide a pseudopolynomial time algorithm for the two-delivery-dates problem based on dynamic programming and some dominance properties. Experimental results are also reported.
  PubDate: 2013-06-01
A new hyper-heuristic as a general problem solver: an implementation in HyFlex
- Abstract: This study provides a new hyper-heuristic design using a learning-based heuristic selection mechanism together with an adaptive move acceptance criterion. The selection process was supported by an online heuristic subset selection strategy. In addition, a pairwise heuristic hybridization method was designed. The motivation behind building an intelligent selection hyper-heuristic using these adaptive hyper-heuristic sub-mechanisms is to facilitate generality. Therefore, the designed hyper-heuristic was tested on a number of problem domains defined in a high-level framework, i.e., HyFlex. The framework provides a set of problems with a number of instances as well as a group of low-level heuristics. Thus, it can be considered a good environment to measure the generality level of selection hyper-heuristics. The computational results demonstrated the generic performance of the proposed strategy in comparison with other tested hyper-heuristics composed of the sub-mechanisms from the literature. Moreover, the performance and behavior analysis conducted for the hyper-heuristic clearly showed its adaptive characteristics under different search conditions. The principles comprising the here presented algorithm were at the heart of the algorithm that won the first international cross-domain heuristic search competition.
  PubDate: 2013-06-01
Solving RCPSP/max by lazy clause generation
- Abstract: We present a generic exact method for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedence relations (Rcpsp/max). This is a very general scheduling model with applications areas such as project management and production planning. Our method uses lazy clause generation, i.e., a hybrid of finite domain and Boolean satisfiability solving, in order to apply no-good learning and conflict-driven search to the solution generation. Our experiments show the benefit of lazy clause generation for finding an optimal solution and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. In comparison to other methods, our method is able to find better solutions faster on the Rcpsp/max benchmarks. Indeed, our method closes 573 open problem instances and generates better solutions in most of the remaining instances. Surprisingly, although ours is an exact method, it outperforms the published non-exact methods on these benchmarks in terms of the quality of solutions.
  PubDate: 2013-06-01
Pareto optimization of rescheduling with release dates to minimize makespan and total sequence disruption
- Abstract: We consider the rescheduling on a single machine with release dates to minimize the makespan and total sequence disruption simultaneously. In the literature, a polynomial-time algorithm was presented for minimizing the makespan under a limit on the total sequence disruption. But the algorithm is not strongly polynomial. We present a strongly polynomial-time algorithm for finding all Pareto optimal points of the Pareto optimization problem. Consequently, the rescheduling to minimize the makespan under a limit on the total sequence disruption can be solved in a strongly polynomial time.
  PubDate: 2013-06-01
Bounded parallel-batching scheduling with two competing agents
- Abstract: We consider a scheduling problem in which two agents, each with a set of non-preemptive jobs, compete to perform their jobs on a common bounded parallel-batching machine. Each of the agents wants to minimize an objective function that depends on the completion times of its own jobs. The goal is to schedule the jobs such that the overall schedule performs well with respect to the objective functions of both agents. We focus on minimizing the makespan or the total completion time of one agent, subject to an upper bound on the makespan of the other agent. We distinguish two categories of batch processing according to the compatibility of the agents. In the case where the agents are incompatible, their jobs cannot be processed in the same batch, whereas all the jobs can be processed in the same batch when the agents are compatible. We show that the makespan problem can be solved in polynomial time for the incompatible case and is NP-hard in the ordinary sense for the compatible case. Furthermore, we show that the latter admits a fully polynomial-time approximation scheme. We prove that the total completion time problem is NP-hard and is polynomially solvable for the incompatible case with a fixed number of job types.
  PubDate: 2013-06-01
A cutting and scheduling problem in float glass manufacturing
- Abstract: This paper considers a cutting and scheduling problem of minimizing scrap motivated by float glass manufacturing and introduces the float glass scheduling problem. We relate it to classical problems in the scheduling literature such as no-wait hybrid flow shops and cyclic scheduling. We show that the problem is NP-hard, and identify when each of the problem’s components are polynomially solvable and when they induce hardness. In addition, we propose a simple heuristic algorithm, provide its worst-case performance bounds, and demonstrate that the bounds are tight. When the number of machines is two, the worst-case performance is 5/3.
  PubDate: 2013-05-25
Perfect periodic scheduling for three basic cycles
- Abstract: Periodic scheduling has many attractions for wireless telecommunications. It offers energy saving where equipment can be turned off between transmissions, and high-quality reception through the elimination of jitter, caused by irregularity of reception. However, perfect periodic schedules, in which each (of $n$ n ) client is serviced at regular, prespecified intervals, are notoriously difficult to construct. The problem is known to be NP-hard even when service times are identical. This paper focuses on cases of up to three distinct periodicities, with unit service times. Our contribution is to derive a $O(n^4)$ O ( n 4 ) test for the existence of a feasible schedule, and a method of constructing a feasible schedule if one exists, for the given combination of client periodicities. We also indicate why schedules with a higher number of periodicities are unlikely to be useful in practice. This methodology can be used to support perfect periodic scheduling in a wide range in real world settings, including machine maintenance service, wireless mesh networks and various other telecommunication networks transmitting packet size data.
  PubDate: 2013-05-17
Stochastic and semidefinite optimization for scheduling in orthogonal frequency division multiple access networks
- Abstract: In this paper, we propose stochastic binary quadratic programs for the scheduling resource allocation process of a wireless orthogonal frequency division multiple access network. More precisely, we formulate a two-stage stochastic model, then we further extend the two-stage model by introducing a knapsack probabilistic constrained approach, and finally we propose a multi-stage stochastic program for this problem. The models are aimed at minimizing the total power consumption of the network at each time slot of the scheduling process subject to user bit rates, sub-carrier and modulation linear constraints. In order to compute lower bounds, we derive linear and semidefinite programming relaxations for each of the proposed models. The bounds are also compared with a basic variable neighborhood search metaheuristic approach. Numerical results show tight lower bounds for the semidefinite relaxations when compared to the linear ones and with the metaheuristic. Moreover, near optimal solutions are found with the semidefinite relaxations for the two-stage model without using probabilistic constraints and for the multi-stage program as well.
  PubDate: 2013-05-10
Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions
- Abstract: This paper addresses the minimization of sequence-dependent setup costs in feeding batch processes. Since feeding batch processes often supply subsequent time-critical stages with modules, hard due date restrictions have to be met. It is common that feeding batch processes possess a specific structure of setup costs that are proportional to resulting machine state differences. If each job has a different batch type, the integration of hard due dates leads to a problem that is equivalent to a specific variant of the Line-TSPTW with general processing times and deadlines. We show that this well-known problem, whose complexity status has been unknown for a long time, is binary $\mathcal{NP }$ NP -hard. Although the more relevant version with a constant number of batch types is known to be strongly polynomial, no practically applicable exact solution method can be found in the literature. Therefore, this paper proposes new solution algorithms. Specifically, Dynamic Programming and Branch&Bound approaches are developed. By making use of a modified problem definition, a new enumeration scheme, and a specifically designed dominance rule, even complex problem instances with up to 200 jobs are optimally solved by a new best-first Branch&Bound algorithm. Apart from a detailed complexity analysis, the efficiency of the proposed approaches is validated by computational experiments.
  PubDate: 2013-05-05
Semi-online scheduling problems on a small number of machines
- Abstract: We consider the semi-online parallel machine scheduling problem of minimizing the makespan given a priori information: the total processing time, the largest processing time, the combination of the previous two or the optimal makespan. We propose a new algorithm that can be applied to the problem with the known total or largest processing time and prove that it has improved competitive ratios for the cases with a small number of machines. Improved lower bounds of the competitive ratio are also provided by presenting adversary lower bound examples.
  PubDate: 2013-05-03
Guest editorial: “New trends in scheduling”
- PubDate: 2013-05-01
A resilience optimization approach for workforce-inventory control dynamics under uncertainty
- Abstract: The presence of uncertainties in manufacturing systems and supply chains can cause undesirable behavior. Failure to account for these in the design phase can further impair the capability of systems to respond to changes effectively. In this work, we consider a dynamic workforce-inventory control problem wherein inventory planning, production releases, and workforce hiring decisions need to be made. The objective is to develop planning rules to achieve important requirements related to dynamic transient behavior when system parameters are imprecisely known. To this end, we propose a resilience optimization model for the problem and develop a novel local search procedure that combines the strengths of recent developments in robust optimization technology and small signal stability analysis of dynamic systems. A numerical case study of the problem demonstrates significant improvements of the proposed solution in controlling fluctuations and high variability found in the system’s inventory, work-in-process, and workforce levels. Overall, the proposed model is shown to be computationally efficient and effective in hedging against model uncertainties.
  PubDate: 2013-04-28
Minimizing total weighted completion time with an unexpected machine unavailable interval
- Abstract: In the past two decades, scheduling with machine availability constraints has received considerable attention. Until recently most research has focused on the setting where all machine unavailability information is known at the beginning of the scheduling horizon. In reality, this is not practical in some cases. The machine may become unavailable to process jobs due to a machine breakdown or an occurrence of an emergent job that has to be processed immediately. In both cases, the start time of the unavailable interval is unknown beforehand, and the length of the interval may not be known until the end of the interval. In this article, we consider the situation in which the scheduler has to make scheduling decisions without any knowledge of the machine unavailable intervals. Of particular interest is the problem of minimizing total weighted completion time. When there are two or more unavailable intervals on a single machine, Fu et al. (2009) have shown that the problem is exponentially inapproximable even when jobs’ weights are equal to their processing times and one has full knowledge of unavailability. So in this paper we consider the scheduling problem on a single machine with a single unavailable period. And, we assume that every job has a weight proportional to its processing time. Based on whether the unavailable interval is due to a breakdown or an emergent job, we have the breakdown model and the emergent job model. First we show that no $\tfrac{\sqrt{5}+1}{2}$ 5 + 1 2 -competitive online algorithm exists for the breakdown model, and no $\tfrac{11-\sqrt{2}}{7}$ 11 − 2 7 -competitive online algorithm exists for the emergent job model. Next, we show that the simple LPT rule can give a 2- and a $\tfrac{9}{5}$ 9 5 -competitive ratio for the breakdown model and the emergent job model, respectively. Further, we show that the ratios are tight by examples. For the offline case, we show that the First Fit LPT (FF-LPT) rule can give a tight approximation ratio of 2 and 4/3 for the breakdown model and the emergent job model, respectively. Finally, our experimental results show that, in practice, both LPT and FF-LPT perform very well and the performance improves when the number of jobs $n$ n increases. In both models, when $n \ge 50$ n ≥ 50 , the worst case error ratio is much better than the theoretical bounds.
  PubDate: 2013-04-18
A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts
- Abstract: In the service industry, workers perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of regular employees are often established several weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands are unveiled with more certainty, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving workers’ meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step, which also involves assigning activities and tasks to the scheduled work shifts. To produce good-quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed-integer programming model is used to suggest temporary shifts and extensions to regular shifts and to schedule and assign tasks. In the second phase, a column-generation heuristic embedded in a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.
  PubDate: 2013-04-16
Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times
- Abstract: We study the problem of maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Unlike the vast majority of the literature, we do not restrict ourselves to a specific model of processing time function. Rather, we assume that the processing time function can be of any functional structure that is according to one of the following two cases. The first is the case where the job processing times are under a learning effect, i.e., each job processing time is a non-increasing function of its position in the sequence. In the second case, an aging effect is assumed, i.e., each job processing time is a non-decreasing function of its position in the sequence. We prove that the problem is strongly $\mathcal{N }\mathcal{P }$ N P -hard under a learning effect, even if all the weights are identical. When there is an aging effect, we introduce a dynamic programming (DP) procedure that solves the problem with arbitrary weights in $O(n^{3})$ O ( n 3 ) time (where $n$ n is the number of jobs). For identical weights, a faster optimization algorithm that runs in $O(n\log n)$ O ( n log n ) time is presented. We also extend the analysis to the case of scheduling on a set of $m$ m parallel unrelated machines and provide a DP procedure that solves the problem in polynomial time, given that $m$ m is fixed and that the jobs are under an aging effect.
  PubDate: 2013-04-13
Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
- Abstract: We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection.
  PubDate: 2013-04-12