Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

The paper considers the single machine due date assignment and scheduling problems with n jobs in which the due dates are to be obtained from the processing times by adding a positive slack q. A schedule is feasible if there are no tardy jobs and the job sequence respects given precedence constraints. The value of q is chosen so as to minimize a function ϕ(F,q) which is non-decreasing in each of its arguments, where F is a certain non-decreasing earliness penalty function. Once q is chosen or fixed, the corresponding scheduling problem is to find a feasible schedule with the minimum value of function F. In the case of arbitrary precedence constraints the problems under consideration are shown to be NP-hard in the strong sense even for F being total earliness. If the precedence constraints are defined by a series-parallel graph, both scheduling and due date assignment problems are proved solvable in time, provided that F is either the sum of linear functions or the sum of exponential functions. The running time of the algorithms can be reduced to if the jobs are independent. Scope and purpose We consider the single machine due date assignment and scheduling problems and design fast algorithms for their solution under a wide range of assumptions. The problems under consideration arise in production planning when the management is faced with a problem of setting the realistic due dates for a number of orders. The due dates of the orders are determined by increasing the time needed for their fulfillment by a common positive slack. If the slack is set to be large enough, the due dates can be easily maintained, thereby producing a good image of the firm. This, however, may result in the substantial holding cost of the finished products before they are brought to the customer. The objective is to explore the trade-off between the size of the slack and the arising holding costs for the early orders.

Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

The emotional costs of caring incurred by men and women in the British labour market

This study investigates whether men and women in caring occupations experience more negative job-related feelings at the end of the day compared to the rest of the working population. The data are from Wave Nine of the British Household Panel Survey (1999) where respondents were asked whether, at the end of the working day, they tended to keep worrying or have trouble unwinding, and the extent to which work left them feeling exhausted or “used up.” Their responses to these questions were used to develop ordinal dependent variables. Control variables in the models include: number of children, age, hours worked per week, managerial responsibilities and job satisfaction, all of which have been shown in previous research to be significantly related to “job burnout.” The results are that those in caring occupations are more likely to feel worried, tense, drained and exhausted at the end of the working day. Women in particular appear to pay a high emotional cost for working in caring occupations. Men do not emerge unscathed, but report significantly lower levels of worry and exhaustion at the end of the day than do women.

Assessing marine plankton community structure from long-term monitoring data with multivariate autoregressive (MAR) models: a comparison of fixed station versus spatially distributed sampling data

We examined how marine plankton interaction networks, as inferred by multivariate autoregressive (MAR) analysis of time-series, differ based on data collected at a fixed sampling location (L4 station in the Western English Channel) and four similar time-series prepared by averaging Continuous Plankton Recorder (CPR) datapoints in the region surrounding the fixed station. None of the plankton community structures suggested by the MAR models generated from the CPR datasets were well correlated with the MAR model for L4, but of the four CPR models, the one most closely resembling the L4 model was that for the CPR region nearest to L4. We infer that observation error and spatial variation in plankton community dynamics influenced the model performance for the CPR datasets. A modified MAR framework in which observation error and spatial variation are explicitly incorporated could allow the analysis to better handle the diverse time-series data collected in marine environments.

Costs and benefits to European shipping of ballast-water and hull-fouling treatment: Impacts of native and non-indigenous species

Maritime transport and shipping are impacted negatively by biofouling, which can result in increased fuel consumption. Thus, costs for fouling reduction can be considered an investment to reduce fuel consumption. Anti-fouling measures also reduce the rate of introduction of non-indigenous species (NIS). Further mitigation measures to reduce the transport of NIS within ballast water and sediments impose additional costs. The estimated operational cost of NIS mitigation measures may represent between 1.6% and 4% of the annual operational cost for a ship operating on European seas, with the higher proportional costs in small ships. However, fouling by NIS may affect fuel consumption more than fouling by native species due to differences in species’ life-history traits and their resistance to antifouling coatings and pollution. Therefore, it is possible that the cost of NIS mitigation measures could be smaller than the cost from higher fuel consumption arising from fouling by NIS.