Popular Matchings with Variable Job Capacities

We consider the problem of matching people to jobs, where each person ranks a subset of jobs in an order of preference, possibly involving ties. There are several notions of optimality about how to best match each person to a job; in particular, popularity is a natural and appealing notion of optimality. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not adroit popular matchings. This motivates the following extension of the popular rnatchings problem:Given a graph G; = (A boolean OR J, E) where A is the set of people and J is the set of jobs, and a list < c(1), c(vertical bar J vertical bar)) denoting upper bounds on the capacities of each job, does there exist (x(1), ... , x(vertical bar J vertical bar)) such that setting the capacity of i-th, job to x(i) where 1 <= x(i) <= c(i), for each i, enables the resulting graph to admit a popular matching. In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c is 1 or 2.

Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler

A model comprising several servers, each equipped with its own queue and with possibly different service speeds, is considered. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. It is shown that if the arrival streams are all Poisson and all jobs have the same exponentially distributed service requirements, the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least-squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times if the service speeds are all equal. This result is used to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream when the load parameters are unknown. The algorithms utilize server idle-time measurements which are sent periodically to the central job scheduler. A model is developed for these measurements, and the result mentioned is used to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed

Independent and mediating organizational commitment effects of trust in leadership on employees' job satisfaction and : a study within social and health care sector

The purpose of this study was to examine whether trust in supervisor and trust in senior management enhance employees' job satisfaction and organizational commitment, and whether trust mediates the relationship between perceived justice and these outcomes. Trust in supervisor was expected to mediate the effects of distributive justice and interactional justice, and trust in senior management was expected to mediate the effects of procedural justice. Theoretical background of the study is based on the framework for trust in leadership developed by Dirks and Ferrin (2002). According to the framework, perceived fairness of leaders' actions helps employees to draw inferences about the basis of the relationship and about leaders' characters. This allows trust formation. Reciprocation of care and concern in the relationship and confidence in leaders' characters are likely to enhance employees' job satisfaction and organizational commitment. This study was conducted with cross-sectional data (A/ = 960) of employees from social and health care sector. Hypotheses were studied using correlation analysis and several hierarchical regression analyses. Significances of the mediations were assessed using the Sobel test. Results partially supported the hypotheses. Trust in leadership was positively related to job satisfaction and organizational commitment. Trust in senior management mediated the relationship between procedural justice and the outcomes. Some support was also found for the mediating effect of trust in supervisor in the relationship between distributive justice and organizational commitment. Due to high correlation between trust in supervisor anil interactional justice, it wasn't possible to study the mediating e fleet of trust in supervisor in the relationship between interactional justice and the outcomes. Against expectations, results indicated that trust in senior management had a mediating effect in the relationship between distributive justice and organizational commitment, and in the relationship between interactional justice and organizational commitment. Results also indicated that trust in supervisor had a mediating effect in the relationship between procedural justice and organizational commitment.

Minimizing total completion time on a batch processing machine with job families

We consider the problem of minimizing the total completion time on a single batch processing machine. The set of jobs to be scheduled can be partitioned into a number of families, where all jobs in the same family have the same processing time. The machine can process at most B jobs simultaneously as a batch, and the processing time of a batch is equal to the processing time of the longest job in the batch. We analyze that properties of an optimal schedule and develop a dynamic programming algorithm of polynomial time complexity when the number of job families is fixed. The research is motivated by the problem of scheduling burn-in ovens in the semiconductor industry

Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families

In this paper, we address a scheduling problem for minimizing total weighted tardiness. The background for the paper is derived from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real-life scenarios like unequal release times, incompatible job families, nonidentical job sizes, heterogeneous batch processors, and allowance for job splitting have been considered. We have developed a mathematical model which takes into account dynamic starting conditions. The problem considered in this study is NP-hard in nature, and hence heuristic algorithms have been proposed to address it. For real-life large-size problems, the performance of the proposed heuristic algorithms is evaluated using the method of estimated optimal solution available in literature. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal statistically estimated solutions in very reasonable computational time.

Decomposing the Gender Wage Gap: The effect of firms, occupations and Job Stratification

This paper presents new evidence on the role of segregation into firms, occupations within a firm and stratification into professional categories within firm-occupations in explaining the gender wage gap. I use a generalized earnings model that allows observed and unobserved group characteristics to have different impact on wages of men and women within the same group. The database is a large sample of individual wage data from the 1995 Spanish Wage Structure Survey. Results indicate that firm segregation in our sample accounts for around one-fifth of the raw gender wage gap. Occupational segregation within firms accounts for about one-third of the raw wage gap, and stratification into different professional categories within firms and occupations explains another one-third of it. The remaining one-fifth of the overall gap arises from better outcomes of men relative to women within professional categories. It is also found that rewards to both observable and unobservable skills, particularly those related to education, are higher for males than for females within the same group. Finally, mean wages in occupations or job categories with a higher fraction of female co-workers are lower, but the negative impact of femaleness in higher for women.

Heuristics for Job-Shop Scheduling

Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure.