Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.02.011 Byline: Rudolf Berghammer (a), Agnieszka Rusinowska (b), Harrie de Swart (c) Keywords: Graph theory; RelView; Relational algebra; Dominance; Stable government Abstract: A stable government is by definition not dominated by any other government. However, it may happen that all governments are dominated. In graph-theoretic terms this means that the dominance graph does not possess a source. In this paper we are able to deal with this case by a clever combination of notions from different fields, such as relational algebra, graph theory and social choice theory, and by using the computer support system RelView for computing solutions and visualizing the results. Using relational algorithms, in such a case we break all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set. In this way we can choose a government that is as close as possible to being un-dominated. To achieve unique solutions, we additionally apply the majority ranking recently introduced by Balinski and Laraki. The main parts of our procedure can be executed using the RelView tool. Its sophisticated implementation of relations allows to deal with graph sizes that are sufficient for practical applications of coalition formation. Author Affiliation: (a) Institute of Computer Science, University of Kiel, Olshausenstra[sz]e 40, 24098 Kiel, Germany (b) GATE, CNRS, Universite Lumiere Lyon 2, 93 Chemin des Mouilles, B.P.167, 69131 Ecully Cedex, France (c) Department of Philosophy, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands Article History: Received 4 December 2006; Accepted 12 February 2008 Article Note: (footnote) [star] Co-operation for this paper was supported by European COST Action 274 'Theory and Applications of Relational Structures as Knowledge Instruments' (TARSKI).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.11.845 Byline: S. Sioutas (a), E. Sakkopoulos (b), Ch. Makris (b), B. Vassiliadis (c), A. Tsakalidis (b), P. Triantafillou (b) Keywords: Web Services Discovery; Peer to Peer overlay networks; Databases Abstract: Service Oriented Computing and its most famous implementation technology Web Services (WS) are becoming an important enabler of networked business models. Discovery mechanisms are a critical factor to the overall utility of Web Services. So far, discovery mechanisms based on the UDDI standard rely on many centralized and area-specific directories, which poses information stress problems such as performance bottlenecks and fault tolerance. In this context, decentralized approaches based on Peer to Peer overlay networks have been proposed by many researchers as a solution. In this paper, we propose a new structured P2P overlay network infrastructure designed for Web Services Discovery. We present theoretical analysis backed up by experimental results, showing that the proposed solution outperforms popular decentralized infrastructures for web discovery, Chord (and some of its successors), BATON (and it's successor) and Skip-Graphs. Author Affiliation: (a) Department of Informatics, Ionian University, 7 Tsirigoti Square, 49100 Corfu, Greece (b) Computer Engineering and Informatics Department, University of Patras, Greece (c) Computer Science, Hellenic Open University, Patras, Greece Article History: Received 18 June 2008; Revised 12 November 2008; Accepted 13 November 2008 Article Note: (footnote) [star] Preliminary version of this paper was presented in Proceedings of IEEE International Conference on Information Technology: Coding and Computing, Next - Generation Web and Grid Systems (IEEE/ITCC 2005), pp. 193-198.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.07.038 Byline: Ya-Shu Chen (a), Li-Pin Chang (b), Tei-Wei Kuo (c), Aloysius K. Mok (d) Keywords: Scheduling anomaly; Real-time task scheduling; Process synchronization; Scheduler stability Abstract: This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies. Author Affiliation: (a) Department of Electronic Engineering, National Taiwan University of Science and Technology, Taipei 106, Taiwan (b) Department of Computer Science, National Chiao-Tung University, Hsin-Chu 300, Taiwan (c) Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan (d) Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA Article History: Received 8 June 2006; Revised 2 July 2008; Accepted 21 July 2008 Article Note: (footnote) [star] This paper is an extended version of the paper that appeared in .

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2008.07.006 Byline: H.C. Wang, C.K. Yuen Keywords: Abstract machine; Java processor; Embedded processor; ILP; VLIW Abstract: Abstract machines bridge the gap between the high-level of programming languages and the low-level mechanisms of a real machine. The paper proposed a general abstract-machine-based framework (AMBF) to build instruction level parallelism processors using the instruction tagging technique. The constructed processor may accept code written in any (abstract or real) machine instruction set, and produce tagged machine code after data conflicts are resolved. This requires the construction of a tagging unit which emulates the sequential execution of the program using tags rather than actual values. The paper presents a Java ILP processor by using the proposed framework. The Java processor takes advantage of the tagging unit to dynamically translate Java bytecode instructions to RISC-like tag-based instructions to facilitate the use of a general-purpose RISC core and enable the exploitation of instruction level parallelism. We detailed the Java ILP processor architecture and the design issues. Benchmarking of the Java processor using SpecJVM98 and Linpack has shown the overall ILP speedup improvement between 78% and 173%. Author Affiliation: Department of Computer Science, School of Computing, National University of Singapore, 3 Science Drive 2, Singapore 117543, Singapore Article History: Received 16 June 2007; Revised 29 April 2008; Accepted 30 July 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.10.025 Byline: Yumei Huo (a), Joseph Y.-T. Leung (b) Keywords: Nested processing set restrictions; Nonpreemptive scheduling; Makespan; NP-hard; Approximation algorithm; Worst-case bound Abstract: We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes a.sub.j and b.sub.j; i.e., job j can only be scheduled on machines a.sub.j,a.sub.j+1,...,b.sub.j. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2-1/m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively. Author Affiliation: (a) Department of Computer Science, CUNY at Staten Island, Staten Island, NY 10314, USA (b) Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA Article History: Received 9 November 2008; Accepted 26 October 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.10.001 Byline: Rong Qu (a), Edmund K. Burke (a), Barry McCollum (b) Keywords: Adaptive; Exam timetabling; Graph colouring; Graph colouring heuristics; Hybridisation; Hyper-heuristic Abstract: In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods. Author Affiliation: (a) Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, University of Nottingham, Wollaton Road, Nottingham NG8 1BB, UK (b) School of Computer Science, Queens University, University Road, Belfast BT7 1NN, N. Ireland, UK Article History: Received 15 August 2006; Accepted 8 October 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.022 Byline: Wenyin Gong, Zhihua Cai Keywords: Multiobjective optimization; Differential evolution algorithm; Pareto-adaptive I[micro] -dominance; Orthogonal design method Abstract: Evolutionary multiobjective optimization has become a very popular topic in the last few years. Since the 1980s, various evolutionary approaches that are capable of searching for multiple solutions simultaneously in a single run have been developed to solve multiobjective optimization problems (MOPs). However, to find a uniformly distributed, near-complete, and near-optimal Pareto front in a small number of fitness function evaluations (NFFEs) is a challenging task for any multiobjective optimization evolutionary algorithm (MOEA). In this paper, we present an improved differential evolution algorithm to MOPs that combines several features of previous evolutionary algorithms in a unique manner. It is characterized by (a) employing the orthogonal design method with quantization technique to generate the initial population, (b) adopting an archive to store the nondominated solutions and employing the new Pareto-adaptive I[micro]-dominance method to update the archive at each generation, (c) storing the extreme points and inserting them into the final archive in order to remedy one of the limitations of I[micro]-dominance: the loss of the extreme points in the final archive, and (d) using a hybrid selection mechanism in which a random selection and an elitist selection are alternated in order to allow using the archive solution to guide the search towards the Pareto-optimal front. Experiments have been conducted on a number of unconstrained real-valued artificial functions of two and three objectives. The results prove the efficiency of our approach with respect to the quality of the approximation of the Pareto-optimal front and the considerable reduction of NFFEs in these test problems. By examining the selected performance metrics, our approach is found to be statistically competitive with five state-of-the-art MOEAs in terms of keeping the diversity of the individuals along the tradeoff surface, finding a well-approximated Pareto-optimal front and reducing the computational effort. Author Affiliation: School of Computer Science, China University of Geosciences, Wuhan 430074, PR China Article History: Received 17 October 2007; Accepted 22 September 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.015 Byline: Jie Zhu, Xiaoping Li, Qian Wang Keywords: No-wait; Job shop; Timetabling; Sequencing Abstract: In this paper, no-wait job shop problems with makespan minimization are considered. It is well known that these problems are strongly NP-hard. The problem is decomposed into the sequencing and the timetabling components. Shift timetabling is developed for the timetabling component. An effective method, CLLM (complete local search with limited memory), is presented by integrating with shift timetabling for the sequencing component. Experimental results show that CLLM outperforms all the existing effective algorithms for the considered problem with a little more computation time. Author Affiliation: School of Computer Science and Engineering, Southeast University, 210096 Nanjing, PR China Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, 210096 Nanjing, PR China Article History: Received 19 October 2007; Accepted 16 September 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.11.846 Byline: Diane Kelly Keywords: Scientific software; Characteristics of scientific software development; Long-term software evolution; Empirical study; Model of change Abstract: One of the characteristics of scientific application software is its long lifetime of active maintenance. There has been little software engineering research into the development characteristics of scientific software and into the factors that support its successful long evolution. The research described in this paper introduces a novel model to examine the nature of change that influenced an example of industrial scientific software over its lifetime. The research uses the model to provide an objective analysis of factors that contributed to long-term evolution of the software system. Conclusions suggest that the architectural design of the software and the characteristics of the software development group played a major role in the successful evolution of the software. The novel model of change and the research method developed for this study are independent of the type of software under study. Author Affiliation: Royal Military College of Canada, Department of Mathematics and Computer Science, Kingston, Ontario, Canada Article History: Received 2 June 2008; Revised 21 November 2008; Accepted 23 November 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.09.013 Byline: Ai Chen, Dongwook Lee, Prasun Sinha Keywords: Wireless LAN; Association control; Algorithm/protocol design; Algorithm/protocol analysis Abstract: Support for efficient multicasting in WLANs can enable new services such as streaming of TV channels, radio channels, and visitor's information. With increasing deployments of large-scale WLANs, such services can be made available to a large number of users. However, any new multicast based services must minimally impact the existing unicast services which are currently the core services offered by most WLANs. In this paper, we leverage the flexibility of associating with different access-points (APs), which occurs often due to overlapping coverage of APs, to optimize the network's objective. Motivated by different revenue functions and network scenarios, three different optimization objectives are considered which are: maximizing the number of admitted users (MNU), balancing the load among APs (BLA), and minimizing the load of APs (MLA). We show that these problems are NP-hard and present centralized approximation algorithms and distributed approaches to solve them. These algorithms compute which AP a user should be associated with. Using simulations we evaluate their performance and compare them to a naive approach in which users associate to the AP with the best RSSI (Received Signal Strength Indicator). Author Affiliation: Department of Computer Science and Engineering, The Ohio State University, 395 Dreese Laboratories, 2015 Neil Avenue, Columbus, OH 43210-1277, USA Article History: Received 15 January 2008; Revised 15 September 2008; Accepted 16 September 2008 Article Note: (miscellaneous) Responsible Editor A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2008.07.004 Byline: Hyungkeun Song (a), Sukwon Choi (a), Hojung Cha (a), Rhan Ha (b) Keywords: Energy-aware embedded systems; Flash memory file system; JFFS2 Abstract: The JFFS2 file system for flash memory compresses files before actually writing them into flash memory. Because of this, multimedia files, for instance, which are already compressed in the application level go through an unnecessary and time-consuming compression stage and cause energy waste. Also, when reading such multimedia files, the default use of disk cache results in unnecessary main memory access, hence an energy waste, due to the low cache hit ratio. This paper presents two techniques to reduce the energy consumption of the JFFS2 flash file system for power-aware applications. One is to avoid data compression selectively when writing files, and the other is to bypass the page caching when reading sequential files. The modified file system is implemented on a PDA running Linux and the experiment results show that the proposed mechanism effectively reduces the overall energy consumption when accessing continuous and large files. Author Affiliation: (a) Department of Computer Science, Yonsei University, Seodaemun-gu, Shinchon-dong 134, Seoul 120-749, Republic of Korea (b) Department of Computer Engineering, Hongik University, Mapo-gu, Sangsoo-Dong 72-1, Seoul 121-791, Republic of Korea Article History: Received 30 June 2006; Revised 18 April 2008; Accepted 14 July 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.03.004 Byline: Yunsong Guo (a), Yanzhi Li (b), Andrew Lim (c), Brian Rodrigues (d) Keywords: Production sourcing; Tariffs; Heuristics Abstract: In this paper, we study a multi-stage production sourcing problem where tariff concessions can be exploited at the firm level using free trade agreements between countries. To solve the problem, an algorithm which embeds a very large-scale neighborhood (VSLN) search into a simulated annealing framework is developed. A numerical study is conducted to verify the effectiveness of the solution approach. Author Affiliation: (a) Department of Computer Science, Cornell University, Ithaca, NY 14853, USA (b) Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong (c) Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (d) Lee Kong Chian School of Business, Singapore Management University, 50 Stamford Road, Singapore 178899, Singapore Article History: Received 14 September 2005; Accepted 21 March 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.01.022 Byline: Rudolf Berghammer (a), Agnieszka Rusinowska (b)(c), Harrie de Swart (d) Keywords: Game theory; RelView; Relational algebra; Coalition formation; Feasible government; Dominance; Stable government Abstract: We present an application of relational algebra to coalition formation. This leads to specifications, which can be executed with the help of the RelView tool after a simple translation into the tool's programming language. As an example we consider a simplification of the situation in Poland after the 2001 elections. Author Affiliation: (a) Institute of Computer Science, University of Kiel, OlshausenstraAe 40, 24098 Kiel, Germany (b) Nijmegen School of Management, Radboud University Nijmegen, P.O. Box 9108, 6500 HK Nijmegen, The Netherlands (c) Department of Mathematical Economics, Warsaw School of Economics, Al. Niepodleglosci 162, 02-554 Warsaw, Poland (d) Department of Philosophy, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands Article History: Received 29 June 2005; Accepted 13 January 2006 Article Note: (footnote) [star] Co-operation for this paper was supported by European COST Action 274 'Theory and Applications of Relational Structures as Knowledge Instruments' (TARSKI). We are grateful to two anonymous referees for some useful suggestions.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.11.024 Byline: S.K. Mishra (a), K.K. Lai (b) Keywords: Second order symmetric duality; Multiobjective programming; Cone-pseudo-invexity Abstract: In this paper, cone-second order pseudo-invex and strongly cone-second order pseudo-invex functions are defined. A pair of Mond-Weir type second order symmetric dual multiobjective programs is formulated over arbitrary cones. Weak, strong and converse duality theorems are established under aforesaid generalized invexity assumptions. A second self-duality theorem is also given by assuming the functions involved to be skew-symmetric. Author Affiliation: (a) Department of Mathematics, Statistics and Computer Science, College of Basic Sciences and Humanities, G.B. Pant University of Agriculture and Technology, Pantnagar 263 145, India (b) Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong and College of Business Administration, Hunan University, Changsha, China Article History: Received 24 September 2004; Accepted 23 November 2005 Article Note: (footnote) [star] The research of first author is supported by the Department of Science and Technology, Ministry of Science and Technology, New Delhi, Government of India under SERC Fast Track Scheme for Young Scientists 2001-2002 through grant No. SR/FTP/MS-22/2001.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.12.015 Byline: Gang Quan (a), Garrison W. Greenwood (b), Donglin Liu (c), Sharon Hu (c) Keywords: Evolutionary computations; Scheduling; Utility theory; Preventive maintenance; Multi-objective optimization Abstract: Heavy industry maintenance facilities at aircraft service centers or railroad yards must contend with scheduling preventive maintenance tasks to ensure critical equipment remains available. The workforce that performs these tasks are often high-paid, which means the task scheduling should minimize worker idle time. Idle time can always be minimized by reducing the workforce. However, all preventive maintenance tasks should be completed as quickly as possible to make equipment available. This means the completion time should be also minimized. Unfortunately, a small workforce cannot complete many maintenance tasks per hour. Hence, there is a tradeoff: should the workforce be small to reduce idle time or should it be large so more maintenance can be performed each hour? A cost effective schedule should strike some balance between a minimum schedule and a minimum size workforce. This paper uses evolutionary algorithms to solve this multiobjective problem. However, rather than conducting a conventional dominance-based Pareto search, we introduce a form of utility theory to find Pareto optimal solutions. The advantage of this method is the user can target specific subsets of the Pareto front by merely ranking a small set of initial solutions. A large example problem is used to demonstrate our method. Author Affiliation: (a) Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA (b) Department of Electrical and Computer Engineering, Portland State University, Portland, OR 97207, USA (c) Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.08.012 Byline: Edmund K. Burke (a), Barry McCollum (b), Amnon Meisels (c), Sanja Petrovic (a), Rong Qu (a) Keywords: Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling Abstract: This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems. Author Affiliation: (a) Automated Scheduling Optimization and Planning Group, School of CSiT, University of Nottingham, Nottingham NG8 1BB, UK (b) School of Computer Science, Queen's University Belfast, Belfast BT7 1NN, UK (c) Department of Computer Science, Ben-Gurion University, Beer-Sheva 84 105, Israel Article History: Received 21 September 2004; Accepted 18 August 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.04.036 Byline: Stef Tijs (a), Rodica Branzei (b), Stefano Moretti (c), Henk Norde (d) Keywords: Cost allocation; Minimum cost spanning tree situations; Cost monotonicity; Population monotonic allocation schemes Abstract: We consider the class of Obligation rules for minimum cost spanning tree situations. The main result of this paper is that such rules are cost monotonic and induce also population monotonic allocation schemes. Another characteristic of Obligation rules is that they assign to a minimum cost spanning tree situation a vector of cost contributions which can be obtained as product of a double stochastic matrix with the cost vector of edges in the optimal tree provided by the Kruskal algorithm. It turns out that the Potters value (P-value) is an element of this class. Author Affiliation: (a) Department of Mathematics, University of Genoa, Italy and CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands (b) Faculty of Computer Science, 'Alexandru Ioan Cuza' University, Carol I Bd., 11, 6600 Iasi, Romania (c) Unit of Molecular Epidemiology, National Cancer Research Institute of Genoa and Department of Mathematics, University of Genoa, Via Dodecaneso, 35, 16146 Genoa, Italy (d) CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands Article History: Received 28 July 2004; Accepted 11 April 2005 Article Note: (footnote) [star] The authors thank two anonymous referees for their careful and valuable comments.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.01.052 Byline: Salem M. Al-Yakoob (a), Hanif D. Sherali (b) Keywords: Timetabling; Class scheduling; Mixed-integer programming; Employee scheduling; Gender policies Abstract: This paper presents mathematical programming models for assigning faculty members to classes including, among typical academic class scheduling issues, certain specialized central policies at Kuwait University. The time-slots for classes are initially assumed to be given and an integer programming model (CFAM) is constructed to solve the resulting problem, which aims to minimize the individual and collective dissatisfaction of faculty members in a fair fashion, where dissatisfaction is measured by a function of the assignment of faculty members to time-slots and specific classes. In order to enhance the quality of results obtained in practice, the model is modified (ECFAM) so that the time-slots for the classes can be changed, however, with restrictions related to efficient facility utilization and permitting an administratively regulated maximum number of changes. Gender-based modeling considerations are also introduced in order to maintain desirable class offering patterns. Computational results are presented based on solving the models directly by the CPLEX-MIP (version 7.5) package and also using a specialized LP-based heuristic. The faculty schedules generated via the proposed approach based on a number of case studies related to the Department of Mathematics and Computer Science at Kuwait University reveal that this approach yields improved schedules in terms of fairness and enhanced satisfaction levels among faculty members. Author Affiliation: (a) Department of Mathematics and Computer Science, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait (b) Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, United States Article History: Received 11 May 2004; Accepted 28 January 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.02.062 Byline: S.K. Mishra (a), S.Y. Wang (b)(d), K.K. Lai (c)(d) Keywords: Multi-objective programming; n-set functions; Optimality; Duality; Generalized convexity Abstract: In this paper, we introduce several generalized convexity for a real-valued set function and establish optimality and duality results for a multi-objective programming problem involving generalized d-type-I and related n-set functions. Author Affiliation: (a) Department of Mathematics, Statistics and Computer Science, College of Basic Sciences and Humanities, Govind Ballabh Pant University of Agriculture and Technology, Pantnagar 263 145, India (b) Institute of Systems Science, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, Beijing 100080, China (c) Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong (d) College of Business Administration, Hunan University, Changsha, China Article History: Received 3 November 2003; Accepted 21 February 2005 Article Note: (footnote) [star] The research was supported by the Department of Science and Technology, Ministry of Science and Technology, Government of India under SERC Fast Track Scheme for Young Scientists 2001-2002 through grant No. SR/FTP/MS-22/2001 and The National Natural Science Foundation of China.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jet.2004.10.007 Byline: Noam Nisan (a), Ilya Segal (b) Abstract: We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to allocate L indivisible items between two agents, a price must be revealed for each of the 2.sup.L-1 bundles. We prove that all monotonic prices for an agent must be used, hence exponential communication in L is needed. Furthermore, exponential communication is needed just to ensure a higher share of surplus than that realized by auctioning all items as a bundle, or even a higher expected surplus (for some probability distribution over valuations). When the utilities are submodular, efficiency still requires exponential communication (and fully polynomial approximation is impossible). When the items are identical, arbitrarily good approximation is obtained with exponentially less communication than exact efficiency. Author Affiliation: (a) Institute of Computer Science, Hebrew University, Jerusalem, Israel (b) Department of Economics, Stanford University, Stanford, CA 94305, USA Article History: Received 10 February 2004; Revised 12 October 2004 Article Note: (footnote) [star] An earlier version of this paper was circulated under the title 'The Communication Complexity of Efficient Allocation Problems.'